T1
只过了这个。模拟样例，将所有 \([i,j]\) 列成一个表格后能很明显找到规律，然后实现的话不好说，看代码。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5*1145140,M=1919810,mod=998244353;
int n,a[N],s13[N],s31[N]; //AC和CA的前缀和计数
char s[N];
ll sum[N],cnt[N];
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>(s+1); n=strlen(s+1);
bool f1=0,f3=0;
for(int i=1;i<=n;++i){
a[i]=s[i]-'A'+1;
s13[i]=s13[i-1];
if(a[i]==1) f1=1;
if(f1&&a[i]==3) f3=1;
if(f1&&f3) s13[i]++,f1=f3=0;
}
f1=f3=0;
for(int i=1;i<=n;++i){
s31[i]=s31[i-1];
if(a[i]==3) f3=1;
if(f3&&a[i]==1) f1=1;
if(f1&&f3) s31[i]++,f1=f3=0;
}
ll las=0,total=0;
for(int i=n;i>=1;--i){
sum[i]=sum[i+1];
if(a[i]!=2){
if(las&&las!=a[i]) sum[i]++;
las=a[i];
}
}
ll ans=0,p=1,del=0;
for(int i=1;i<=n;++i){
++cnt[sum[i]],total+=sum[i];
if(sum[i]) ++del;
}
for(int i=n;i>=1;--i){
ans+=total,ans%=mod;
if(a[i]!=2&&(s13[i]!=s13[i-1]||s31[i]!=s31[i-1])) total-=del,del-=cnt[p],++p;
//必须是这个位置减了贡献也会相应减去才行，用AC/CA的前缀和计数判断
}
cout<<ans;
return 0;
}
T2
区间dp，没看出来，但是看出来了就好做了。
因为是个环，所以先破环成链，注意战胜的关系也要对应赋值。
设 \(dp[i][j]\) 表示 \(i,j\) 是否可能相邻，若相邻则默认 \(i\) 挑战 \(j\)，因为破环成链了所以不影响。枚举 \(i,j\) 都可到达的点 \(k\)，即满足 \(dp[i][k]=dp[k][j]=\mathbf{1}\)，若 \(i\) 能战胜 \(k\) 或 \(k\) 不能战胜 \(j\)，那么 \(dp[i][j]=\mathbf{1}\)
对于每个 \(i\)，若 \(dp[i][i+n]=\mathbf{1}\)，则 \(i\) 可以是最后赢家。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=2*1145,M=1919810,mod=998244353;
ll n,a[N][N],dp[N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
cin>>a[i][j],a[i+n][j]=a[i][j+n]=a[i+n][j+n]=a[i][j];
for(int len=2;len<=2*n;++len)
for(int i=1;i<=2*n-len+1;++i){
int j=i+len-1;
if(len==2) dp[i][j]=1;
for(int k=i+1;k<j;++k)
if(dp[i][k]&&dp[k][j]&&(a[i][k]||!a[k][j])) dp[i][j]=1;
}
for(int i=1;i<=n;++i)
if(dp[i][i+n]) cout<<i<<" ";
return 0;
}
T3
找规律题，应该做的。首先乘数中有 \(\mathbf{0}\) 的行和列肯定都是相同的一个对应 \(\mathbf{0}\) 的值，先找出来。然后找规律，会对于每一行/列，其变量对应的值就是这一行/列中不同的十位数的个数。具体证明不会。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=2*1145,M=1919810,mod=998244353;
ll n,a[N][N],b[N][N],ans[N],num[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=0;i<n;++i){
ans[i]=-1;
for(int j=0;j<n;++j)
cin>>a[i][j]>>b[i][j];
}
for(int j=0;j<n;++j){
bool fl=0;
for(int i=0;i<n-1;++i)
if(a[i][j]!=a[i+1][j]||b[i][j]!=b[i+1][j]) fl=1;
if(!fl) ans[j]=0;
}
for(int j=0;j<n;++j){
ll tot=0;
for(int i=0;i<n;++i) num[i]=0;
for(int i=0;i<n;++i)
if(!num[a[i][j]]) ++tot,num[a[i][j]]=1;
if(ans[j]==-1) ans[j]=tot;
}
for(int i=0;i<n;++i) cout<<ans[i]<<" ";
return 0;
}
T4
应该补不了，不过我的搜索实现得确实太劣了……
标签：mathbf,int,提高,cin,模拟,20240420,tie,ll,dp From： https://www.cnblogs.com/heshuwan/p/18147716