Loading... ## Problem A. Ervin and Joker 显然，只要Ervin能把中间的一个或者两个拿走使之隔开，那么就能形成“复读机”局势，那么Ervin必胜。 显然，Joker获胜的情况只有以下两种： - $n=0$ - $k=1\ \&\&\ n\%2=0$ ```cpp #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int n,k; int main() { scanf("%d%d",&n,&k); if(n==0) { printf("Joker\n"); } else if(k==1&&n%2==0) { printf("Joker\n"); } else { printf("Ervin\n"); } return 0; } ``` ## Problem B. 炼金大师小D 题面可能有点问题，但本质是一道最短路。可以转化成一个二维地图，从$s$点到$e$点的最小特殊步数。但是因为珍惜物品是放入有序的，所以要多开一维枚举用到了哪一件珍惜物品。 $dp[i][j][k]$用到第k件物品到$(i,j)$点的最短路。 也有bfs的做法。 ```cpp #include <bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f struct no{ int x,y,w,v; bool operator <(const no &a)const{ return v>a.v; } }; struct nn{ int x,y; };nn d1[110],d2[110]; int n,m,k; int f[110][110],vis[110][110][55],dk[110][110][55]; priority_queue<no>q; void gdk(int ux,int uy) { if(f[0][0]) { puts("impossible!"); return ; } memset(dk,inf,sizeof(dk)); q.push((no){0,0,1,dk[0][0][1]=0}); while(!q.empty()) { no p=q.top();q.pop(); if(!vis[p.x][p.y][p.w])vis[p.x][p.y][p.w]=1; else continue; for(int i=1;i<=n;i++) { int x=p.x+d1[i].x,y=p.y+d1[i].y; if(x<0||x>100||y<0||y>100)continue; if(vis[x][y][p.w])continue; if(f[x][y])continue; if(dk[x][y][p.w]>dk[p.x][p.y][p.w]) q.push((no){x,y,p.w,dk[x][y][p.w]=dk[p.x][p.y][p.w]}); } for(int i=p.w;i<=m;i++) { int x=p.x+d2[i].x,y=p.y+d2[i].y; if(x<0||x>100||y<0||y>100)continue; if(vis[x][y][i])continue; if(f[x][y])continue; if(dk[x][y][i]>dk[p.x][p.y][p.w]+1) q.push((no){x,y,i,dk[x][y][i]=dk[p.x][p.y][p.w]+1}); } } int ans=inf; for(int i=1;i<=m;i++) ans=min(dk[ux][uy][i],ans); if(ans==inf)puts("impossible!"); else printf("%d\n",ans); } int main() { int x,y; scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d %d",&d1[i].x,&d1[i].y); for(int i=1;i<=m;i++) scanf("%d %d",&d2[i].x,&d2[i].y); for(int i=1;i<=k;i++) scanf("%d %d",&x,&y), f[x][y]=1; scanf("%d %d",&x,&y); gdk(x,y); return 0; } ``` ## Problem C. 良心出题人又来啦 ！ ~~由于良心出题人不小心良心了，~~直接通过线性筛等方法筛出素数然后暴力就完了~ ~~（出题人说下次要给你们放大数据的，所以不给你们他的标程了！~~ ## Problem D. 小D的递减序列 建立$k$棵线段树，每颗线段树存的是长度为$m(1 \leq m \leq k）$的结尾为$num(0\leq num \leq 10^5)$的递减序列的个数，每颗线段树存的序列的长度是固定的。然后从头到尾扫一遍给定的序列，然后对于每一个数，从线段树中找到结尾大于当前数字且长度小于$k$的所有序列，然后添加进入线段树中，最后把存长度为$k$的线段树的所有序列求和取模。 ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; #define ls i*2+1 #define rs i*2+2 #define mid (l+r)/2 typedef long long ll; const int mod=1e9; ll dp[400100][20]; struct tr{ int l,r; ll v; };tr t[20][400010]; void t0(int k,int l,int r ,int i){ tr tree={l,r,0LL}; t[k][i]=tree; if(l==r)return ; t0(k,l,mid,ls),t0(k,mid+1,r,rs); } ll t1(int k,int l,int r,int i){ if(t[k][i].l==l&&t[k][i].r==r)return t[k][i].v; if(l>=t[k][rs].l)return t1(k,l,r,rs); if(r<=t[k][ls].r)return t1(k,l,r,ls); return (t1(k,l,t[k][ls].r,ls)+t1(k,t[k][rs].l,r,rs))%mod; } void t2(int k,int p,ll v,int i){ if(t[k][i].l==t[k][i].r){ t[k][i].v=(t[k][i].v+v)%mod; return ; } if(p>=t[k][rs].l)t2(k,p,v,rs); else t2(k,p,v,ls); t[k][i].v=(t[k][ls].v+t[k][rs].v)%mod; } int main() { int k,v,n; ll ans=0; scanf("%d %d",&n,&k); for(int i=0;i<k;i++)t0(i,0,100002,0); for(int i=0;i<n;i++){ scanf("%d",&v); for(int j=k;j>=1;j--){ if(j==1)dp[i][j]=1; else dp[i][j]=t1(j-1,v,100002,0); if(j<k)t2(j,v,dp[i][j],0); } ans=(ans+dp[i][k])%mod; } cout<<ans<<endl; return 0; } ``` ## Problem E. 争夺宇宙魔方 其实就是一个bfs搜索一下就完事了~数据问题，表示深表歉意~~（其实是题面少打了一个0~~ ```cpp #include<cstdio> #include<algorithm> #include<iomanip> #include<math.h> #include<cstring> #include<iostream> #include<stack> #include<queue> #include<functional> #include<set> #include<vector> #include<stdlib.h> using namespace std; int n,m,vis[1010][1010]; char map[1010][1010]; int dist[1010][1010]; const int dx[]={-1,0,1,0,-1,-1,1,1}; const int dy[]={0,1,0,-1,1,-1,1,-1}; struct dot{ int x,y; dot(int x1,int y1){ x=x1; y=y1; } }; queue<dot>q; void bfs(){ int x,y,i,j; while(!q.empty()){ dot now=q.front(); q.pop(); for(i=0;i<4;i++){ x=now.x+dx[i]; y=now.y+dy[i]; if(vis[x][y]||map[x][y]=='T'||x<0 || y<0 || x>=n || y>=m )continue; else { q.push(dot(x,y)); dist[x][y]=dist[now.x][now.y]+1; vis[x][y]=1; } } } } int main(){ int sx,sy,ex,ey,i,j,k; while(scanf("%d%d",&n,&m)!=EOF){ memset(dist,0,sizeof(dist)); memset(vis,0,sizeof(dist)); while(!q.empty())q.pop(); for(i=0;i<n;i++){getchar(); for(j=0;j<m;j++){ scanf("%c",&map[i][j]); if(map[i][j]=='S'){ sx=i; sy=j; } if(map[i][j]=='E'){ ex=i; ey=j; } } } q.push(dot(ex,ey)); vis[ex][ey]=1; bfs(); int res=0; for(i=0;i<n;i++){ for(j=0;j<m;j++){ if((i==sx&&j==sy)||(i==ex&&j==ey))continue; if(vis[i][j]!=0&&dist[i][j]<=dist[sx][sy]){ res+=map[i][j]-'0'; } } } printf("%d\n",res); } } ``` ## Problem F. 小D的光玉 二分答案，$x$越大，$n$个光玉所能分的组就越多，显然可以二分$x$，如果$x=mid$所能分的组小于等于$m$满足条件，如果大于$m$说明$mid$太小了，二分查找$x$的最小值。 ```cpp #include <bits/stdc++.h> using namespace std; int a[100005]; int check(int mid, int n, int m) { int i, j, k; int sum = 0; int ans = 0; for(i = 1; i <= n; i++) { if(sum + a[i] <= mid)sum += a[i]; else { sum = a[i]; ans++; } } ans++; if(ans <= m)return 1; else return 0; } int main() { int n, m, i, j, k; scanf("%d %d", &n, &m); for(i = 1; i <= n; i++) { scanf("%d", &a[i]); } int ans = 1, l = 1, r = 1e9; while(l <= r) { // cout << l << " " << r << endl; int mid = (l + r) / 2; if(check(mid, n, m)) { r = mid - 1; ans = mid; } else l = mid + 1; } printf("%d\n", ans); } ``` ## Problem G. 谢神的交换数问题 考虑下标的置换，可以发现最少的交换次数等于$n$减去置换中循环的数量，所以可以枚举所有的n 排列解决此题。对于每个置换，只需要检查它是否可以在$k$次交换内实现并更新答案。期望时间复杂度是$O(n!)$。为了实现期望复杂度可能需要在搜索和回溯过程中高效维护链和环的信息。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; int seq[11]; int num[11]; int times; bool vis[11]; int len; bool count() { int cnt = 0; memset(vis, 0, sizeof(bool) * len); for (int i = 0; i < len; i++) { if (vis[i] == 0) { int tmp = 0; while (vis[i] == 0) { vis[i] = 1; tmp++; i = seq[i]; } cnt += tmp - 1; if (cnt > times) return 0; } } return 1; } char s[15]; int main() { int T; cin >> T; while (T--) { scanf("%s%d", s, ×); len = strlen(s); int minnum = 1e9 + 100; int maxnum = 0; for (int i = 0; i < len; i++) { num[i] = s[i] - '0'; seq[i] = i; } do { if (num[seq[0]] != 0 && count()) { int ret = 0; for (int i = 0; i < len; i++) ret = ret * 10 + num[seq[i]]; minnum = min(minnum, ret); maxnum = max(maxnum, ret); } } while (next_permutation(seq, seq + len)); cout << minnum << " " << maxnum << endl; } } ``` ## Problem H. 小D的训练 $dp [ i ] [ j ] [ k]$，$i$ 是天数，$j$ 是当前精力值，三维的数组是没问题的，也有空间小的写法(滚动数组优化掉第一维)，$k$ 是对当前第$i$天来说连续休息了几天（0代表没休息，1 代表 1 天，2 代表 2 天），$dp$ 存的是最大的能力提高值。 ```cpp #include <bits/stdc++.h> using namespace std; typedef int ll; ll dp[100001][101][3]; ll a[100001], d[100001]; int main() { ll n, m, i, j, k, ki; scanf("%d %d %d",&n,&m,&k); for(i = 1; i <= n; i++)scanf("%d", &a[i]); for(i = 1; i <= n; i++)scanf("%d", &d[i]); memset(dp, -1, sizeof(dp)); dp[0][m][0] = 0; ll ans = -0x3f3f3f; for(i = 1; i <= n; i++) { for(j = 0; j <= m; j++) { dp[i][min(m, j + k)][1] = max(dp[i - 1][j][0], dp[i][min(m, j + k)][1]); dp[i][min(m, j + k)][2] = max(dp[i - 1][j][1], dp[i][min(m, j + k)][2]); if(j >= d[i]) { dp[i][j - d[i]][0] = max(dp[i - 1][j][0], max(dp[i - 1][j][1], dp[i - 1][j][2])); if(dp[i][j - d[i]][0] != -1) { dp[i][j - d[i]][0] += a[i]; } } } } for(j = 0; j <= m; j++) { for(i = 0; i <= 2; i++) { ans = max(ans, dp[n][j][i]); } } printf("%d\n", ans); return 0; } ``` ## Problem I. 魔法盒子 首先打表，$magic[l][r]$，代表从$l$到$r$的子串的魔力值，枚举字符串中心点，注意考虑到长度为奇偶两种情况，增量构造，复杂度$O(n^2)$ 然后对于每次询问，二分答案，找到最长的符合要求的子串，每次询问复杂度$O(log\ n)$ ```cpp #include<iostream> #include<cstring> #define DEBUG 0 using namespace std; int query[6005][6005]; int abs(int a) { return a>0?a:-a; } int bsearch3(int l,int r,int n,int key){ int left = 0; int right = n; //降序排列，查找第一个小于或等于key的元素 // 这里必须是 <= while (left <= right) { int mid = (left + right) / 2; if (-query[l+mid][r-mid] >= -key) {//这里改成负数 right = mid - 1; } else { left = mid + 1; } } return left; } int main() { int T,q; // scanf("%d",&T); char s[6005]; // for(int I=1; I<=10; I++) { char f[1000]; // sprintf(f,"%d.in",I); // freopen(f,"r",stdin); // sprintf(f,"%d.out",I); // freopen(f,"w",stdout); scanf("%s",s+1); memset(query,-1,sizeof query); int l=strlen(s+1); //预处理 //以奇数为中轴 int i,j; for(i=1; i<=l; i++) { query[i][i]=0; for(j=1; i-j>=1 && i+j<=l; j++) { query[i-j][i+j]= query[i-j+1][i+j-1]+ abs(0+s[i-j]-s[i+j]); } } //以奇数为中轴 for(i=1; i<=l-1; i++) { query[i][i+1]=abs(0+s[i]-s[i+1]); for(j=1; i-j>=1 && i+1+j<=l; j++) { query[i-j][i+1+j]= query[i-j+1][i+j+1-1]+ abs(0+s[i-j]-s[i+1+j]); } } if(DEBUG)for(i=1;i<=l;i++){ for(j=1;j<i;j++)printf("0 "); for(j=i;j<=l;j++){ printf("%d ",query[i][j]); } printf("\n"); } scanf("%d",&q); for(i=1; i<=q; i++) { int l,r,t; scanf("%d %d %d",&l,&r,&t); //二分搜索 int k=(r-l+1)/2; printf("%d\n",r-l+1-2*bsearch3(l,r,k,t)); // for(;query[l][r]>t;l++,r--); // printf("%d\n",r-l+1); } // } } ``` ## Problem J. 小D的子序列 思维题 ，遍历序列分别处理每一个0的位置，对一个0之前的数求后缀和到前一个0停止，对0之后的数求前缀和也是到下一个0停止，`map`记录个数统计答案即可。 详解：满足题目要求的子序列中如果有多个零，那么任意两个零之间的和一定为零。所以可以从序列从前向后跑一遍，不断更新答案，当遇到零的时候，需要更新后缀和出现的个数，如果当前零与上一个零之间所有数的和为零，即会有满足题目要求的序列存在多个零，那么前面记录的后缀和就不用清除，如果不为零，则说明包括当前零和上一个的序列不满足题目要求，则上一个零之前记录的后缀和的出现次数就清空。 ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long #define N 1000005 map<ll,int>mp; ll a[N]; int main() { int n,i=0; scanf("%d",&n); for(int j=1;j<=n;j++) scanf("%lld",&a[j]); a[++n]=1e13; ll ans=0,sum; while(++i<=n) { ans+=mp[sum=0]; for(i;a[i]!=0&&i<=n;i++) ans+=mp[sum+=a[i]]; if(sum)mp.clear(); if(!mp.count(sum=0))mp[sum]=1; else mp[sum]++; for(int j=i-1;a[j]!=0;j--) { sum+=a[j]; if(!mp.count(sum))mp[sum]=1; else mp[sum]++; } } printf("%lld\n",ans); return 0; } ``` ## Problem K. 情报特工 出题人的做法是暴力将所有询问大小矩阵哈希后哈希表查询即可。标算似乎是hash+kmp，后缀数组好像也可以做。~~不过由于数据过水，被一位打星神仙直接暴力比较对角线上数据莽过了……~~ ```cpp #include<cstdio> #include<iostream> #include<cstring> #define ull unsigned long long using namespace std; const int maxn=1013; const int modd=23333333; ull pre[maxn][maxn],v[maxn][maxn],jc[maxn]; int n,m,a,b,q; char s[maxn]; bool u[23333333]; int main(){ register int i,j,k; scanf("%d%d%d%d",&n,&m,&a,&b); for(i=jc[0]=1;i<=m;i++)jc[i]=jc[i-1]*233; for(i=1;i<=n;i++){ scanf("%s",s+1); for(j=1;j<=m;j++)pre[i][j]=pre[i][j-1]*233+s[j]; if(i==a) for(j=b;j<=m;j++) for(k=1;k<=i;k++)v[i][j]=v[i][j]*233+pre[k][j]-pre[k][j-b]*jc[b]; else if(i>a) for(j=b;j<=m;j++)v[i][j]=v[i-1][j]*233+pre[i][j]-pre[i][j-b]*jc[b]-(pre[i-a][j]-pre[i-a][j-b]*jc[b])*jc[a]; } for(i=1;i<=n;i++)for(j=1;j<=m;j++)u[v[i][j]%modd]=1; scanf("%d",&q); while(q--){ ull now=0,now1; for(i=1;i<=a;i++){ scanf("%s",s+1); for(now1=0,j=1;j<=b;j++)now1=now1*233+s[j]; now=now*233+now1; } bool flag=u[now%modd]; //for(i=a;i<=n&&!flag;i++)for(j=b;j<=m;j++)if(v[i][j]==now){flag=1;break;} // puts(flag?"1":"0"); printf("%s\n",flag?"known":"new"); } return 0; } ``` ## Problem L. 肥宅大哭.jpg 按照题意，按照$D_i$排序然后计算即可。 ```cpp #include <bits/stdc++.h> using namespace std; void work() { int n, m; scanf("%d%d" , &n , &m); vector<pair<int, int>> a(n); for (int i = 0 ; i < n ; ++ i) { scanf("%d" , &a[i].first); } for (int i = 0 ; i < n ; ++ i) { scanf("%d" , &a[i].second); } sort(a.begin() , a.end()); int res = 0; for (int i = 0 ; i < n ; ++ i) { if (m >= a[i].second) { ++ res; m -= a[i].second; } else { break; } } static int ca = 0; printf("Case %d: %d\n" , ++ ca , res); } int main() { int T; scanf("%d" , &T); while (T --) { work(); } } ``` ## Problem M. 31点 ### 方法1： （这是出题人想要的方案）考虑这个游戏的实质就是1-6的选数博弈问题，但是由于每个数字有限，所以会存在一些特殊情况，如$(n,m)=(5,5),(1,1),(1,2)$，只要把这些情况考虑清楚即可，其他时候无脑拼7。完整的情况如下图所示（包括$n=2$的）： - 先手拿 5 - 假如后手拿 5，先手接着拿 2，后手再拿 5 先手继续 2…… - 假如后手拿非 5 的，先手就在下一次拿取中抢占关键点 3、10、17、24、31，抢到之后后手拿 X 先手就拿 7-X - 先手拿1： <img src="https://image.mlwly.cn/2019/05/14/5cda0a762739e.jpg" alt="e61190ef76c6a7eff48bd97bf3faaf51f3de6639.jpg" /> - 先手拿2： <img src="https://image.mlwly.cn/2019/05/14/5cda0a865a201.jpg" alt="b21c8701a18b87d6e36bdd42090828381f30fd46.jpg" /> 对应的程序实现如下： ```cpp #include <bits/stdc++.h> using namespace std; int num[7]={0,4,4,4,4,4,4}; int sum=0; void play() { while (sum!=31) { int x=31-sum; x%=7; assert(num[x]); printf("%d\n",x); num[x]--; sum+=x; fflush(stdout); scanf("%d",&x); if (x<=0) return; num[x]--; sum+=x; } } int main() { int n,m; scanf("%d%d",&n,&m); num[n]--; num[m]--; sum=n+m; if ((n==5&&m!=5)||(n==1&&m>=3)) { play(); return 0; } if (n==5&&m==5) { while (1) { printf("2\n"); fflush(stdout); num[2]--; sum+=2; int x; scanf("%d",&x); if (x<=0) return 0; num[x]--; sum+=x; if (x!=5) { play(); break; } } } if (n==1) { bool flag=(m==2); while (1) { printf("6\n"); fflush(stdout); num[6]--; sum+=6; int x; scanf("%d",&x); if (x<=0) return 0; num[x]--; sum+=x; if (x>=3) { play(); break; } if (x==2) { if (flag) { play(); break; } flag=true; continue; } } } return 0; } ``` ### 方法2： 不过验题人发现，这题步数很少，直接暴力搜索，把所有情况搜到，找到所有的必胜情况即可，为了代码的美观，可以使用状压等技巧 ```cpp #include<stdio.h> #include<string.h> int state[5*5*5*5*5*5]; int nextplay[5*5*5*5*5*5]; int go(int nowstate){ if(state[nowstate])return state[nowstate]; int a[7],sum=0; for(int i=1,temp=nowstate;i<=6;i++){ a[i]=temp%5; sum+=a[i]*i; temp/=5; } if(sum==31)return state[nowstate]=-1; if(sum>31)return state[nowstate]=1; for(int i=1,temp=1;i<=6;i++){ if(a[i]<4&&go(nowstate+temp)==-1){ nextplay[nowstate]=i; return state[nowstate]=1; } temp*=5; } return state[nowstate]=-1; } int w[7]; int main() { w[1]=1; for(int i=2;i<=6;i++) w[i]=w[i-1]*5; int nowstate=0; int n,m; scanf("%d",&n); nowstate+=w[n]; int x; while(~scanf("%d",&x)){ nowstate+=w[x]; go(nowstate); printf("%d\n",nextplay[nowstate]); fflush(stdout); nowstate+=w[nextplay[nowstate]]; } return 0; } ``` Last modification：May 14th, 2019 at 08:24 am © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
