本次比賽由大四金牌團隊出題
A - Array Permutation
題意： 思維題，輸入n，現有m位的陣列array（m<n），從[ 1，n-m ]中隨機生成x，將[ 1，2，3…x ]排列到array后面組成新陣列，直到陣列有n位，求對于特定的n有幾種不同的陣列
思路：
①模擬一下結果就是2n-1 .
②這題要用快速冪 ，不然會超時
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b%2==1)
{
res*=a;
res%=mod;
}
b/=2;
a*=a;
a%=mod;
}
return res;
}
int main()
{
ll n,t;
cin>>t;
while(t--)
{
cin>>n;
ll x;
x=qpow(2,n-1)%mod;
cout<<x<<endl;
}
return 0;
}
H - Hsueh- And Treasure
題意： T組資料，每組輸入寶藏坐標（x，y），每次從（0,0）出發，第t秒內可以走t個單位，輸出到達目標的最短時間和每秒結束后的實時坐標，注意：第t秒內必須精準地走完t個單位，不多不少，
思路： 模擬題，
代碼實作大概分這些步驟：
①初始化、處理坐標、特判
②建構式：先走橫坐標
③建構式：再走縱坐標
④建構式：處理剩余步數
⑤判斷奇偶后處理或轉化
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1e5+5;
int t,walk,dis;
//t為時間 walk為該秒可走步數 dis為剩余步數
ll xi[maxn],yi[maxn],x,y,fx,fy,xx,yy;
//xi陣列和yi陣列為實時位置 fx和fy是坐標的正負性
void remanent() //處理剩余步數
{ //如果剩余步數與相差步數同奇偶 可一秒走完
//否則總是走到距離目標值的一步之距--->轉化成同奇偶的情況
if((y-yy)%2==1)
{
if(dis%2==1)
{
t++;
xi[t]=xx*fx;
yi[t]=y*fy;
}
else
{
t++;
xi[t]=xx*fx;
yi[t]=(y-1)*fy;
t++;
xi[t]=xx*fx;
yi[t]=y*fy;
}
}
else
{//dis為奇數可以實作走到一步之距
//為偶數可以實作待在原地
if(dis%2==0)
{
t++;
xi[t]=xx*fx;
yi[t]=y*fy;
}
else
{
t++;
xi[t]=xx*fx;
yi[t]=(y+1)*fy;
t++;
xi[t]=xx*fx;
yi[t]=(y+1)*fy;
t++;
xi[t]=xx*fx;
yi[t]=y*fy;
}
}
}
void walky() //再走縱坐標
{
if(dis>=y) //剩余步數>縱坐標
{
remanent(); //處理剩余步數
return;
}
yy+=dis;
t++;
xi[t]=xx*fx;
yi[t]=yy*fy;
walk++;
while(1)
{
yy+=walk;
if(yy>=y)
{ //縱坐標超過目標值 撤回上一秒的操作
dis=walk; //撤回后剩余步數為walk
yy-=walk; //撤回后縱坐標
remanent(); //通過繞遠路來耗完剩余步數
return;
}
walk++; //更新一系列變數
t++;
xi[t]=xx*fx;
yi[t]=yy*fy;
}
}
void walkx() //先走橫坐標
{
while(1)
{
xx+=walk;
if(xx>=x) //走完橫坐標
{
dis=xx-x; //這一秒內剩余可走步數
xx=x;
walky(); //再走縱坐標
return;
}
//更新橫縱坐標和時間、步數
walk++;
t++;
xi[t]=xx*fx;
yi[t]=yy*fy;
}
}
int main()
{
int T;
scanf("%d",&T);
for(int tt=1;tt<=T;tt++)
{
scanf("%lld%lld",&x,&y);
printf("Case #%d:\n",tt);
xx=0,yy=0,t=0,dis=0,walk=1;
fx=1,fy=1; //考慮正負號
if(x<0) fx=-1;
if(y<0) fy=-1;
x=abs(x);
y=abs(y);
if(x==0&&y==0) printf("0\n"); //(0,0)特判
else
{
walkx(); //先走橫坐標
printf("%d\n",t);
for(int i=1;i<=t;i++)
printf("%lld %lld\n",xi[i],yi[i]);
}
}
return 0;
}
I - Iaom and Chicken feet
題意： 存圖，找最多有幾個有形如上圖的“雞爪”圖形，要求每個雞爪要是不同邊集的，
思路： ①先要搞清楚題意，“雞爪”圖形是上面一整個，不是一部分 ②找準合適的節點有規律地分析
觀察可知，雞腿 需要除父節點外的兩條邊/點 ，爪子 需要除父節點外的三條邊/點 ，
∴只需對兩部分排列組合后相乘 即可，示例中雞腿部分為sum=C（deg[2]-1，2），爪子部分為res=C（deg[4]，3）
同理，用dfs從根節點開始不斷遍歷鄰居即可，要注意一些特判情況，考慮到資料范圍，組合數需要用快速冪再取模，
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+5;
const ll mod = 998244353;
int n;
ll ans,deg[maxn],s[maxn];;
int cnt, head[maxn];
struct edge
{
int v, next;
}e[maxn*2];
void add (int u,int v) //存邊
{
e[++cnt] = {v, head[u]}; head[u] = cnt;
e[++cnt] = {u, head[v]}; head[v] = cnt;
}
void init() //s陣列存n的階乘n!
{
s[0] = 1;
s[1] = 1;
for(ll i = 2; i <= 500000; i++)
s[i] = s[i - 1] * i % mod;
}
ll qpow(ll n,ll k) //快速冪
{
ll ans=1;
while(k)
{
if(k&1)
ans=ans*n%mod;
n=n*n%mod;
k/=2;
}
return ans;
}
ll C(ll n,ll m) //組合數
{
if(n<m) return 0;
return s[n]*qpow(s[n-m]*s[m]%mod,mod-2)%mod;
}
void dfs1(int u,int fa)
{ //從根節點開始遍歷相鄰的點 記錄每個節點入度
deg[u]=0;
for (int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if (v==fa) continue;
dfs1(v, u);
deg[u]++;
}
}
void dfs2(int u,int fa)
{
ll res=0,sum;
//res sum分別負責統計爪子和雞腿上的情況
if(fa!=0) sum=deg[u]+1;
else sum=deg[u];
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)
{
if(fa==1&°[fa]>=4)
res=(res+C(deg[fa]-1,3))%mod;
if(fa!=1&°[fa]>=3)
res=(res+C(deg[fa],3))%mod;
}
else
{
dfs2(v,u);
if(deg[v]>=3)
res=(res+C(deg[v],3))%mod;
}
}
ans=(ans+res*C(sum-1,2))%mod;
}
int main()
{
scanf("%d",&n);
init();
memset(deg,0,sizeof(deg));
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
}
dfs1(1,0);
dfs2(1,0);
printf("%lld",ans);
return 0;
}
J - Jew Sorting
題意： 輸入k，給出2k 個數，操作：每次平分兩段，可舍棄任一部分，直到留下的序列為非降序則結束，求最少需要幾次操作
思路： 每次截取2k 的區間，依次遍歷查詢每個區間，查完再二分重復從頭遍歷，直到有找到非降序列結束，
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+1e5;
int k,a[maxn];
int main()
{
scanf("%d",&k);
int n=1<<k;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int l=1,r=n,num=0,len=n;
for(int i=l;i<r;i++)
{
if(a[i]<=a[i+1]) continue; //符合條件 能順利跳出for回圈說明是非降序列
else //下一組or繼續二分
{
if(l+len>n) //已是當前最后一組 繼續二分
{
len/=2;
num++;
l=1;
r=l+len-1;
i=l-1;
if(len==1) break;
}
else //跳至下一組區間
{
l+=len;
r+=len;
i=l-1;
}
}
}
printf("%d",num);
return 0;
}
也可以用線段樹 做（顯然我寫不出），這里貼一篇很好的科普博客—>傳送門
碼還是參照鐵子哥的（代碼作者：Sstee1XD）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1e5;
int ans = 1;
int a[N], k, n;
struct Seg
{
int minn[N << 2], maxx[N << 2];
bool flag[N << 2];
void up(int id, int l, int r) //向上更新線段樹
{
if (flag[id << 1 | 1] && flag[id << 1] && maxx[id << 1] <= minn[id << 1 | 1])
{ //即id*2+1
flag[id] = true;
minn[id] = minn[id << 1];
maxx[id] = maxx[id << 1 | 1];
ans = max(r - l + 1, ans);
}
}
void build(int id, int l, int r) //建樹
{
flag[id] = false;
minn[id] = 0;
maxx[id] = 0;
if (l == r)
{
flag[id] = true;
maxx[id] = a[l];
minn[id] = a[l];
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
up(id, l, r);
}
}seg;
void solve()
{
scanf("%d", &k);
int n = 1 << k; //即k=2^k
for (int i = 1; i<= n; ++i) scanf("%d", &a[i]);
seg.build(1, 1, n);
printf("%d\n", k - __lg(ans));
}
int main() {
int t = 1;
while(t--) solve();
return 0;
}
K - K-Clearing II
題意： 輸入n m k，n個數，每m個數一組，進行清除操作，統計每組操作結束后有幾個數為0，最后累加，注意 ，每次操作結束后，原陣列的資料不會改變，
思路： 求每組有幾個從k開始的連續的不同的數，再求每個不同的數的個數，最后累加，直接用for回圈會超時，要建兩棵線段樹降低時間復雜度，
①第一棵線段樹統計當前區間的[k,k+m]有幾個連續不同的數，統計出該區間需要減去的數sum
②第二棵線段樹統計各個不同的數的個數，再依次累加
③遍歷每棵線段樹
沒想到吧 根本不會寫 哈哈:)
或者用樹狀陣列 （碼是鐵子哥的，菜雞還沒完全看明白嗚嗚，來個大佬寫個注釋吧嗚嗚）（代碼作者：Sstee1XD）
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
typedef long long ll;
int n, q, m, k, idk;
int a[N], b[N], id[N];
ll tot[N], had[N];
int num[N];
int lowbit(int x) {
return x & -x;
}
void add(int i, ll v, ll bit[]) {
while (i <= q) {
bit[i] += v;
i += lowbit(i);
}
}
ll query(int i, ll bit[]) {
ll res = 0;
while (i > 0) {
res += bit[i];
i -= lowbit(i);
}
return res;
}
void ins(int i) {
if (!num[i]) {
add(i, 1ll, had);
}
add(i, 1ll, tot);
num[i]++;
}
void del(int i) {
num[i]--;
add(i, -1ll, tot);
if (!num[i]) {
add(i, -1ll, had);
}
}
ll gao(int u, int v) {
if (!num[idk]) return 0;
ll res = 0;
int l = idk + 1, r = q, mid;
while (l <= r) {
mid = l + r >> 1;
ll tmp = query(mid, had) - query(idk - 1, had);
if (tmp < mid - idk + 1) r = mid - 1;
else l = mid + 1;
}
int len = b[l - 1] - b[idk] + 1;
int pos = lower_bound(b + 1, b + 1 + q, len) - b;
if (pos > q || b[pos] > len) pos--;
if (pos <= 0) return 0;
len = pos;
return query(len, tot);
}
void solve() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + 1 + n);
q = unique(b + 1, b + 1 + n) - b - 1; //去重函式
//q為去重后尾元素下標 即有幾個不同的數
int Q = q;
for (int i = 2; i <= q; ++i) {
if (b[i] - b[i - 1] > 1) {
b[++Q] = b[i] - 1;
}
}
q = Q;
sort(b + 1, b + 1 + q);
for (int i = 1; i <= n; ++i) {
id[i] = lower_bound(b + 1, b + 1 + q, a[i]) - b;
if (a[i] == k) idk = id[i];
}
if (!idk) {
puts("0");
return;
}
ll ans = 0;
for (int i = 1; i <= m; ++i) {
ins(id[i]);
}
for (int i = 1; i + m - 1 <= n; ++i) {
if (i != 1) {
del(id[i - 1]);
ins(id[i + m - 1]);
}
ans += gao(i, i + m - 1);
}
printf("%lld\n", ans);
}
int main() {
int t = 1;
while(t--) solve();
return 0;
}
后記
這次省賽選拔賽簽到題都沒做完要反省，
一個是因為幾個人都沒有去準備，直接裸考，自己準備的紙質材料也沒有，只有幾本沒看過的演算法書，
還有一個是因為確實實力也還沒有，其實J挺水，如果靜下來好好去想，在賽場上應該還是能寫出的，當時幾個人狀態都不積極覺得會是比較復雜的二分題，還因為覺得寫回圈必超時就根本沒去寫 （這邊建議要是怕超時以后用個clock（）函式—>傳送門）
希望自己可以這兩個月堅持多多刷題，爭取六月份個人選拔賽可以留下來呆在實驗室，
還要繼續加油吶，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272571.html
標籤：其他