网站优化怎样做外链,印章生成器,wordpress文章图片滑动,手机app游戏制作软件文章目录前言考场复盘T1 roadT2 shopT3 runT4 stairs总结前言
240分 100802040 T3少取了一个模结果全挂掉了#xff08;好不容易推出来了…#xff09; T2也因为各种奇怪的错误挂了分 qwq 吸取教训吧
考场
今天先看题 T1第一眼看错了题意觉得水的不行 T3YBT原题且很水 T2T…
文章目录前言考场复盘T1 roadT2 shopT3 runT4 stairs总结前言
240分 100802040 T3少取了一个模结果全挂掉了好不容易推出来了… T2也因为各种奇怪的错误挂了分 qwq 吸取教训吧
考场
今天先看题 T1第一眼看错了题意觉得水的不行 T3YBT原题且很水 T2T4乍看不太可做
因为错误审题决定先写自以为很水的T1 写完样例不对才发现自己审题完全审错了 那个翻折的关键性质又没有看出来都看出来了吗我感觉并不显然啊qwq 分析了一会性质感觉打表或许可行 但可能是道搬砖题 此时大概8:40 于是转T3稳一稳
此时心态有些不稳了 我甚至觉得T3的3e7会炸 把T3超级暴力的《正解》floyd敲完还不太放心 但是也没有什么太好的方法 转回T1死磕 9:30
T1走上了慢慢打表之路 打了30min终于把恶心的转移数组敲完了 此时已经感觉药丸 但是编译结果有点惊喜 一遍过了样例 又测了几个位置也对了 说实话那个搬砖代码一个bug没有真的挺神奇的 我本来已经做好了和它死磕的准备 结果就这么过了 重新燃起希望 10:20
来到T2 很不错的时我很快发现了它的关键性质 利用一半为分界点递归转移 然后后面再跟个二分 check的地方递归求个数 很愉快的切掉了这道挺难的题 有一说一这道应该是我这几次模拟做的最好的一道题 确实有逻辑分析在里面 遗憾的是我切掉的时候也有点激动 手一抖最后的一步乘法没有取模 … 11:00
此时 我以为 我已经切了3题 心态就平和了起来 推了一会T4没有任何思路 就决定写个好一点的部分分下班 20分还是很好写的 40分也不太难 又开始暴力搬砖 11:30
这次时间有些紧凑 T1和T3浪费了太多时间 我没有很多的时间检查了 说不定再看看T2的沙雕错误就瞅出来了呢qwq 最后就带着那个bug走出了考场 qwq
复盘
T1 road
正解简单的离谱 关键是回溯时对原图进行一个神奇的反转操作 就很easy了 但为了纪念还是附上打表代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e6100;
int n;
int a,b;
int mi[32];
int shunpl[5][5]{{},{0,1,1,1,3},{0,4,2,2,2},{0,3,1,3,3},{0,4,4,2,4}};
int shundir[5][5]{{},{0,2,1,1,2},{0,2,2,1,1},{0,1,2,2,1},{0,1,1,2,2}};
int shunid[5][5]{{},{0,1,2,3,4},{0,4,1,2,3},{0,3,4,1,2},{0,2,3,4,1}};
int nipl[5][5]{{},{0,1,3,1,1},{0,2,2,4,2},{0,3,3,3,1},{0,2,4,4,4}};
int nidir[5][5]{{},{0,1,1,2,2},{0,2,1,1,2},{0,2,2,1,1},{0,1,2,2,1}};
int niid[5][5]{{},{0,1,4,3,2},{0,2,1,4,3},{0,3,2,1,4},{0,4,3,2,1}};
int dx[5]{0,0,0,1,1},dy[5]{0,0,1,1,0};
/*
1:shun
2:ni
*/
int x2,y2,x3,y3;
void find(int k,int pl,int dir,int id,int x,int y){int edidmi[2*k]-1;if((aid||aed)(bid||bed)) return;if(k0){if(ida){x2x;y2y;}if(idb){x3x;y3y;}return;}if(dir1){//shunint lenmi[k-1],totmi[(k-1)*2];for(int i1;i4;i){find(k-1,shunpl[pl][i],shundir[pl][i],id(shunid[pl][i]-1)*tot,xdx[i]*len,ydy[i]*len);}return;}else{int lenmi[k-1],totmi[(k-1)*2];for(int i1;i4;i){find(k-1,nipl[pl][i],nidir[pl][i],id(niid[pl][i]-1)*tot,xdx[i]*len,ydy[i]*len);}return;}
}
int main(){
// freopen(road.in,r,stdin);
// freopen(road.out,w,stdout);int t;scanf(%d,t);mi[0]1;for(int i1;i30;i) mi[i]mi[i-1]1;while(t--){scanf(%d%d%d,n,a,b);find(n,1,1,1,1,1);//printf(a(%d,%d) b(%d,%d)\n,x2,y2,x3,y3);printf(%.0lf\n,10.0*sqrt((x3-x2)*(x3-x2)(y3-y2)*(y3-y2)));}return 0;
}
/*
3
1 1 2
2 16 1
3 4 33
*/T2 shop
本题std的二分很神奇 类似于一个二分相对大小的最大值 然后硬限制一个范围 就过了… 觉得还是我的代码更好理解一写qwq所有人对自己的代码都是这么想的 不取模见祖宗
#includebits/stdc.h
using namespace std;
#define ll long long
const int N105;
const int mod1e97;
int n,k;
int solve(int x){if(x0) return 0;return xsolve(x/2);
}
int find(int l,int r){if(lr) return 0;if(r0) return 0;return r-l1 find((l1)/2,r/2);
}
ll ksm(ll x,int k){ll ans1,resx;while(k){if(k1) ansans*res%mod;resres*res%mod;k1;}return ans;
}
void work(int k,int n){int totsolve(n/2);if(ktot){work(k,n/2);return;}k-tot;
// printf(n%d tot%d k%d\n,n,tot,k);int ok/n,pk%n;if(p0){printf(%lld\n,n*ksm(2,o-1)%mod);return;}int stn/21,edn;while(sted){int midsted1;
// printf( l%d r%d find%d\n,n/21,mid,find(n/21,mid));if(find(n/21,mid)p) edmid;else stmid1;}printf(%lld\n,st*ksm(2,o)%mod);
}
int main(){
// freopen(shop.in,r,stdin);
// freopen(shop.out,w,stdout);int t;scanf(%d,t);while(t--){scanf(%d%d,k,n);work(k,n);}return 0;
}
/*
5
3 1
3 2
5 3
1000000000 1
987654321 8765432101
32 10
*/T3 run
YBT原题且很水 这也挂分就离谱 有一个是没有特判m1的情况 还有一个是因为int的范围k只枚举到30而不是31 头疼
#includebits/stdc.h
using namespace std;
#define ll long long
const int N105;
int n,m;
bool f[33][N][N];
int dis[N][N];
int main(){
// freopen(run.in,r,stdin);
// freopen(run.out,w,stdout);int t;scanf(%d,t);while(t--){memset(f,0,sizeof(f));memset(dis,0x3f,sizeof(dis));
// if(n1){
// printf(0\n);
// continue;
// }scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);f[0][x][y]1;}for(int k1;k30;k){for(int i1;in;i){for(int j1;jn;j){//if(ij) continue;for(int p1;pn;p){//if(pi||pj) continue;if(f[k-1][i][p]f[k-1][p][j]){f[k][i][j]1;
// printf( p%d\n,p);break;}}
// printf(k%d i%d j%d f%d\n,k,i,j,f[k][i][j]);}}}for(int i1;in;i){for(int j1;jn;j){//if(ij) continue;for(int k0;k30;k){if(f[k][i][j]){
// printf(ok:k%d i%d j%d\n,k,i,j);dis[i][j]1;break;}}}dis[i][i]0;}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}}}printf(%d\n,dis[1][n]);}return 0;
}
/*
1
5 5
1 4
4 1
1 2
2 3
3 5
*/T4 stairs
这题考场确实不太可做 考后写起来发现反而不难了 状压求出转移矩阵再快速幂加速即可 一个重要的技巧是把0规定为有挡板 这样不同高度之间可以无缝连接
#includebits/stdc.h
using namespace std;
#define ll long long
const int N105;
const int mod1e97;
int n,k;
int w[8];
struct matrix{int x,y;ll a[130][130];void clear(){for(int i0;ix;i)for(int j0;jy;j) a[i][j]0;}
};
int mi[8];
void print(matrix o){for(int i0;imin(3,o.x);i){for(int j0;j3;j) printf(%d ,o.a[i][j]);printf(\n);}return;
}
matrix cheng(matrix a,matrix b){matrix o;//printf(Mul:\n) ;//print(a);print(b);o.xa.x;o.yb.y;o.clear();for(int i0;io.x;i){for(int j0;jo.y;j){for(int k0;ka.y;k){o.a[i][j](o.a[i][j]a.a[i][k]*b.a[k][j])%mod;//if(a.a[i][k]*b.a[k][j]) printf( i%d j%d k%d %d*%d a%d\n,i,j,k,a.a[i][k],b.a[k][j],o.a[i][j]);}}}return o;
}
int dp[130][2];//dp[i][op]op:下面的边
matrix trans[8];
void init(){mi[0]1;for(int i1;i7;i) mi[i]mi[i-1]1;for(int k1;k7;k){trans[k].xtrans[k].ymi[7]-1;for(int i0;imi[k];i){for(int j0;jmi[k];j){dp[0][1]1;dp[0][0]0;for(int p1;pk-1;p){if((i|j)mi[p-1]){dp[p][1]dp[p-1][0]dp[p-1][1];dp[p][0]dp[p-1][1]dp[p-1][0];}else{dp[p][1]dp[p-1][0];dp[p][0]dp[p-1][1]dp[p-1][0];}dp[p][0]%mod;dp[p][1]%mod;}if((i|j)mi[k-1]) trans[k].a[i][j]dp[k-1][0]dp[k-1][1];else trans[k].a[i][j]dp[k-1][0];//printf(k%d i%d j%d trans%d\n,k,i,j,trans[k].a[i][j]);}}}
}
matrix ans;
int main(){for(int i1;i7;i) scanf(%d,w[i]);init();ans.x0;ans.ymi[7]-1;ans.a[0][0]1;for(int i1;ians.y;i) ans.a[0][i]0;for(int k1;k7;k){//printf(k%d trans:\n,k);//print(trans[k]);while(w[k]){//printf(k%d\n,w[k]);if(w[k]1){anscheng(ans,trans[k]);//printf(ans:\n);//for(int i0;i4;i) printf(%d ,ans.a[0][i]);//printf(\n);}trans[k]cheng(trans[k],trans[k]);//printf(trans:\n);//print(trans[k]);w[k]1;}}printf(%lld\n,ans.a[0][0]);return 0;
}
/*
5
3 1
3 2
5 3
1000000000 1
987654321 8765432101
32 10
*/总结
争取吃一堑长一智吧 以后检查代码注意的东西又多了一个取模是否彻底 明天字符串 加油awa
