总结
T1 T2
考场上上很快就打出了正解没什么问题。
T3
考场上也打出了正解，但被卡常了。
T4
考场上想到了正解，但还没有来得及打就结束了。
T5
考场上想到了一个部分分解，但是时间复杂度误认为是正解，所以就没有往正解去想。
题解
T1
我们只需要保证它是手指的个数的倍数以及它能够被我们最小最大之间才行。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,m,q,sum=0;cin>>n>>m>>q;for(int i=1;i<=n;i++){char c;cin>>c;sum+=m*(c-'0');}while(q--){int x;cin>>x;if(x%m!=0||x<sum||x>sum+m*n) cout<<"No"<<endl;else cout<<"Yes"<<endl;}return 0;
}
T2
不难发现，这道题我们可以设立一个向上走的一个向下走的，那么每一次我们从父亲结点或者子节点转移过来即可。
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e5+5;
int u[maxn],d[maxn],a[maxn];
vector<int> g[maxn];
void dfs(int x,int fa)
{d[x]^=d[fa];for(auto to:g[x]){dfs(to,x);u[x]^=u[to];}
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,m;cin>>n>>m;for(int i=2;i<=n;i++){int x;cin>>x;g[x].push_back(i);}for(int i=1;i<=n;i++) cin>>a[i];while(m--){int op,x,v;cin>>op>>x>>v;if(op==1) d[x]^=v;else u[x]^=v;}dfs(1,0);for(int i=1;i<=n;i++) cout<<(a[i]^u[i]^d[i])<<' ';return 0;
}
T3
会发现这道题我们移动了N步之后。地图会回到原来初始的状态。
所以我们只需要在原来的广搜状态下再多开一维即可。表示当前正在跑哪一种地图
注意，这里每一个点我都要判断这一张地图以及下一张地图能否过，而终点只需要判断这一张地图即可。
代码
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=401;
int dis[maxn][maxn][maxn],a[maxn][maxn][maxn];
int n,sx,sy,Tx,Ty;
int dx[5]={1,0,-1,0,0};
int dy[5]={0,1,0,-1,0};
char mp[maxn][maxn];
struct node
{int x,y,k;
};
pair<int,int> mv(int x,int y,char op,int m)
{if(op=='U') x=x-m+n;if(op=='D') x=x+m;if(op=='L') y=y-m+n;if(op=='R') y=y+m;x=(x-1)%n+1,y=(y-1)%n+1;return {x,y};
}
bool in(int x,int y)
{return x<=n&&x>=1&&1<=y&&y<=n;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>sx>>sy>>Tx>>Ty;for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cin>>mp[i][j];for(int k=0;k<n;++k){for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){dis[k][i][j]=-1;if(mp[i][j]=='.') continue;int x=mv(i,j,mp[i][j],k).first,y=mv(i,j,mp[i][j],k).second;a[k][x][y]=1;}}}dis[0][sx][sy]=0;queue<node> q;q.push({sx,sy,0});while(!q.empty()){node now=q.front();q.pop();int x=now.x,y=now.y,k=now.k;for(int i=0;i<5;++i){int tx=x+dx[i],ty=y+dy[i],tk=(k+1)%n;if(in(tx,ty)&&dis[tk][tx][ty]==-1&&!a[k][tx][ty]){if(Tx==tx&&Ty==ty){cout<<dis[k][x][y]+1;return 0;}if(!a[tk][tx][ty]) dis[tk][tx][ty]=dis[k][x][y]+1,q.push({tx,ty,tk});}}}cout<<-1;return 0;
}
T4
有一个非常显然的性质，局部最优解一定可以推导至全局最优解。
所以我们考虑分治。
不难发现，如果说当前这一段的两端均被一个大于等于二的数包裹住那么此时这一段一定全部选加或者全部选乘。
而对于那些两端只有一的一定选加
发现如果有取模的情况下，无法比大小
可以记录是否大于 \(10^9\)，如果大于就立刻选乘法
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5,mod=998244353;
string s;
pair<int,int> f(int l,int r)
{stack<int> stk;vector<pair<int,int> > v;int cnt=0;for(int i=l;i<=r;i++){if(s[i]=='(') stk.push(i);else if(s[i]==')'){if(stk.size()==1) v.push_back(f(stk.top()+1,i-1));stk.pop();}if(stk.empty()&&s[i]=='x') v.push_back({1,0});}int lt,rt;for(lt=0;lt<v.size();lt++){if(v[lt].first>1||v[lt].second==1) break;cnt++;}for(rt=v.size()-1;;rt--){if(v[rt].first>1||v[rt].second==1||rt<lt) break;cnt++;}int cnt1=0,cnt2=1,f=0;for(int i=lt;i<=rt;i++){if(v[i].second==1||cnt2*v[i].first>1e9) f=1;cnt1=(cnt1+v[i].first)%mod;cnt2=cnt2*v[i].first%mod;}if(rt<lt) cnt2=0;// cout<<l<<' '<<r<<'|'<<lt<<' '<<rt<<':'<<cnt<<' '<<max(cnt1,cnt2)<<endl;if(f==1) return {cnt+cnt2,1};else return {(cnt+max(cnt1,cnt2))%mod,0};
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){cin>>s;s=' '+s;cout<<f(1,s.size()-1).first<<endl;}return 0;
}
T5
容易发现最后的结果其实只有一到五的情况需要特判大于六的我们直接令 \(a_i=i \mod 4\)，即可
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t;cin>>t;while(t--){int n;cin>>n;if(n==1) cout<<1<<endl<<1<<endl;if(n==2) cout<<2<<endl<<"1 2"<<endl;if(n==3) cout<<2<<endl<<"1 2 2"<<endl;if(n==4) cout<<3<<endl<<"1 2 2 3"<<endl;if(n==5) cout<<3<<endl<<"1 2 2 3 3"<<endl;if(n>=6){cout<<4<<endl;for(int i=1;i<=n;i++) cout<<i%4+1<<' ';cout<<endl;}}return 0;
}