陕西网站建设的目的,深圳工程建设交易服务中心网站,模仿别人网站,蓝牙小程序开发教程比赛链接
反思
T1
奇怪的贪心和构造题一直是我的软肋部分
T2
简单题
T3
也不难
T4
套路没学过#xff0c;感觉还是太菜了
题解
A
考虑先给图随便染色#xff0c;然后调整 因为每个点的度数为 3 3 3#xff0c;所以如果有 x → u → v x\to u\to v x→u→v 的颜…比赛链接
反思
T1
奇怪的贪心和构造题一直是我的软肋部分
T2
简单题
T3
也不难
T4
套路没学过感觉还是太菜了
题解
A
考虑先给图随便染色然后调整 因为每个点的度数为 3 3 3所以如果有 x → u → v x\to u\to v x→u→v 的颜色全部相同那么修改 u u u 的颜色一定能使 u u u 符合条件然后就用队列存储调整的点一直调整即可 估算一下时间复杂度是 O ( n ) O(n) O(n) 级别的肯定不会调整很多次
#include bits/stdc.h
#define pb push_back
using namespace std;
const int N200100;
int col[N],deg[N];
bool inq[N];
vectorint G[N];
queueint que;
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void upd(int x){deg[x]0;for(int v:G[x]) if(col[v]col[x]) deg[x];if(deg[x]2!inq[x]) inq[x]1,que.push(x);
}
void work(){int nread(),mread();while(!que.empty()) que.pop();for(int i1;in;i) G[i].clear(),inq[i]0;for(int i1;im;i){int xread(),yread();G[x].pb(y),G[y].pb(x);}for(int i1;in;i) col[i]0;for(int i1;in;i) upd(i);int cnt0;while(!que.empty()){int uque.front();que.pop();inq[u]0;if(deg[u]2) continue;cnt;if(cntm) break;col[u]^1;upd(u);for(int v:G[u]) upd(v);}if(!que.empty()) puts(GG);else{for(int i1;in;i) printf(%d ,col[i]);puts();return;}
}
int main(){freopen(classical.in,r,stdin);freopen(classical.out,w,stdout);int Tread();while(T--) work();fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
B
感觉这才是本场比赛的签到题 可以发现操作类似冒泡排序然后手玩一下样例发现答案为逆序对数 无解情况判一下奇偶性即可 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
#include bits/stdc.h
#define lowbit(x) x-x
using namespace std;
typedef long long LL;
typedef pairint,int pii;
const int N1000100;
int n,p[N],tr[N],a[2][N],b[2][N];
pii pos[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void add(int x){ for(;xn;xlowbit(x)) tr[x];}
int ask(int x){int res0;for(;x;x-lowbit(x)) restr[x];return res;
}
int main(){freopen(rotate.in,r,stdin);freopen(rotate.out,w,stdout);nread();for(int i1;in;i) a[0][i]read();for(int i1;in;i) a[1][i]read();for(int i1;in;i) b[0][i]read();for(int i1;in;i) b[1][i]read();for(int i1;in;i) pos[b[0][i]]{0,i},pos[b[1][i]]{1,i};//check -1for(int i1;in;i){int xa[0][i];if(!pos[x].firstpos[x].secondi) continue;if(((pos[x].first-i)1)!(pos[x].second1)){ puts(-1);exit(0);}}for(int i1;in;i) p[i]pos[a[0][i]].second;LL ans0;for(int in;i1;i--) ansask(p[i]),add(p[i]);printf(%lld\n,ans);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
C
这道题最重要的想法是分治 考虑对于左上角 ( x 1 , y 1 ) (x_1,y_1) (x1,y1)右下角 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 的矩形求出覆盖矩形内所有 1 1 1 的方案数这可以枚举行和列的分割线递归下去求解 时间复杂度 O ( n 5 ) O(n^5) O(n5)需要加一些剪枝就能卡过去了
#include bits/stdc.h
using namespace std;
bool Mbe;
const int N65;
int n,s[N][N],f[N][N][N][N];
bool a[N][N];
char str[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
inline void chkmin(int x,int y){ if(yx) xy;}
int calc(int lx,int ly,int rx,int ry){ return s[rx][ry]-s[lx-1][ry]-s[rx][ly-1]s[lx-1][ly-1];}
int solve(int lx,int ly,int rx,int ry){auto tf[lx][ly][rx][ry];if(t!-1) return t;if(!calc(lx,ly,rx,ry)){ t0;return 0;}if(rx-lx1ry-ly1){bool flg1;for(int ily;iry;i) if(!calc(lx,i,rx,i)){ flg0;break;}if(flg){ try-ly1;return t;}}else{bool flg1;for(int ilx;irx;i) if(!calc(i,ly,i,ry)){ flg0;break;}if(flg){ trx-lx1;return t;}}tmax(rx-lx1,ry-ly1);//枚举分割线for(int ilx;irx;i){int tmpsolve(lx,ly,i,ry);if(tmpt) chkmin(t,tmpsolve(i1,ly,rx,ry));}for(int jly;jry;j){int tmpsolve(lx,ly,rx,j);if(tmpt) chkmin(t,tmpsolve(lx,j1,rx,ry));}return t;
}
bool Med;
int main(){freopen(detection.in,r,stdin);freopen(detection.out,w,stdout);// fprintf(stderr,%.3lf MB\n,(Mbe-Med)/1048576.0);nread();for(int i1;in;i){scanf(%s,str1);for(int j1;jn;j) a[i][j]str[j]T;}for(int i1;in;i) for(int j1;jn;j) s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j];memset(f,-1,sizeof(f));printf(%d\n,solve(1,1,n,n));fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
D
感觉是套路题 首先 O ( n 2 ) O(n^2) O(n2) 的树形 d p dp dp 是好做的 考虑 k 1 k1 k1 的部分分这一部分有一个经典的想法考虑答案即为 ∏ s i z 每一个联通快 \prod siz_{每一个联通快} ∏siz每一个联通快直接做仍是 O ( n 2 ) O(n^2) O(n2) 的重要考虑它的组合意义即为在每个连通块内选一个点的方案数这个可以令 f i , 0 / 1 f_{i,0/1} fi,0/1 表示 i i i 所在的连通块是否选过点的方案和时间复杂度 O ( n ) O(n) O(n)期望得分 50 p t s 50pts 50pts
考虑一步转化是 s k ∑ i 0 k { k i } s i ‾ ∑ i 0 k { k i } ( s i ) i ! s^k\sum\limits_{i0}^{k}{k\brace i}s^{\underline{i}}\sum\limits_{i0}^{k}{k\brace i}\binom{s}{i}i! ski0∑k{ik}sii0∑k{ik}(is)i! 考虑 { k i } k\brace i {ik} 和 i ! i! i! 都是好算的主要是 ( s i ) \binom{s}{i} (is)这个可以根据组合意义用 d p dp dp 计算即令 f i , j f_{i,j} fi,j 为 i i i 的联通快内选 j j j 个点的方案和但 j ≤ k j\le k j≤k所以时间复杂度 O ( n k ) O(nk) O(nk)
#include bits/stdc.h
using namespace std;
const int N100100,K110,P1e97;
int n,m,fac[K],siz[N],t[K];
int e[N],ne[N],h[N],idx;
int stir2[K][K];
int f[N][K],g[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void add(int x,int y){ e[idx]y,ne[idx]h[x],h[x]idx;}
void dfs(int u){f[u][0]f[u][1]1,siz[u]1;for(int ih[u];~i;ine[i]){int ve[i];dfs(v);for(int j0;jmin(m,siz[u]siz[v]);j) t[j]0;for(int j0;jsiz[u];j) t[j]1ll*f[u][j]*g[v]%P;// for(int j0;jm;j) coutt[j] ;cout\n;for(int j0;jsiz[u];j) for(int k0;kmin(siz[v],m-j);k)t[jk](t[jk]1ll*f[u][j]*f[v][k])%P;siz[u]min(m,siz[u]siz[v]);for(int j0;jsiz[u];j) f[u][j]t[j];}for(int i0;im;i) g[u](g[u]1ll*stir2[m][i]*fac[i]%P*f[u][i])%P;
}
int main(){freopen(calc.in,r,stdin);freopen(calc.out,w,stdout);nread(),mread();stir2[0][0]1;for(int i1;im;i)for(int j1;ji;j) stir2[i][j](stir2[i-1][j-1]1ll*j*stir2[i-1][j])%P;fac[0]1;for(int i1;im;i) fac[i]1ll*fac[i-1]*i%P;memset(h,-1,sizeof(h));for(int i2;in;i) add(read(),i);dfs(1);printf(%d\n,g[1]);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
