杭电多校2023“钉耙编程”中国大学生算法设计超级联赛（5）

1006	Touhou Red Red Blue

dp

设状态方程为前i个数中，当前第一个包里面的是0/1/2/3状态，第二个包里面是0/1/2/3状态

0代表着还没有颜色，1代表R，2代表G，3代笔B颜色

初始状态都没选择颜色所以都是状态0

没选择颜色只能从后面的字符里面选

细想操作一 a b两个包清空，然后a选择任意颜色，b从后面的选，

换句话说就是a的颜色要取决于后面的颜色，所以不如直接让b变成任意颜色，a状态变成0

后面选择的字符放到a，其实是等效的，且这样遍历

else f[i][b][c]=max(f[i][b][c],f[i-1][a][b]);

我不用另外判断这个条件

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,mod=998244353;typedef long long LL;
typedef pair<int, int> PII;int n;
int f[N][5][5];
int get(char c){if(c=='R') return 1;else if(c=='G') return 2;else return 3;
}void solve(){memset(f,-0x3f,sizeof(f));string s;cin>>s;n=s.size();s="?"+s;f[0][0][0]=0;for(int i=1;i<=n;i++){int c=get(s[i]);for(int a=0;a<=3;a++){for(int b=0;b<=3;b++){f[i][a][b]=f[i-1][a][b];}}for(int a=0;a<=3;a++){for(int b=0;b<=3;b++){if(a==b&&b==c){for(int d=1;d<=3;d++){f[i][0][d]=max(f[i][0][d],f[i-1][a][b]+1);}}else if(a&&b&&c&&a!=b&&a!=c&&b!=c){for(int d=1;d<=3;d++){for(int e=1;e<=3;e++){f[i][d][e]=max(f[i][d][e],f[i-1][a][b]);}}}else f[i][b][c]=max(f[i][b][c],f[i-1][a][b]);}}}int res=0;for(int a=0;a<=3;a++){for(int b=0;b<=3;b++)res=max(res,f[n][a][b]);}cout<<res<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

1012	Counting Stars

首先统计度数

k星图可以由

k+1星图选择去掉其中1条边里面的其中一条变成

k+2星图选择去掉其中2条边里面的其中两条变成

...

所以直接统计度数即可

然后每个点暴力枚举2到d[i]的k星图增加个数即可

复杂度是n+m

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
int n,m,k;
int fact[N],infact[N];
int qmi(int a, int k, int p)  // 求a^k mod p
{int res = 1 % p;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}void init(){fact[0] = infact[0] = 1;for (int i = 1; i < N; i ++ ){fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;}
}
int C(int a,int b){if(b>a) return 0;return ((LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
void solve(){int n,m;cin>>n>>m;vector<int> d(n+10,0),ans(n+10,0);for(int i=1;i<=m;i++){int a,b;cin>>a>>b;d[a]++,d[b]++;}for(int i=1;i<=n;i++){long long tmp=d[i]*(d[i]-1)/2%mod;for(int j=2;j<=d[i];j++){ans[j]=(ans[j]+C(d[i],j))%mod;}} long long res=0;for(int i=2;i<=n-1;i++)res^=ans[i];cout<<res<<"\n";
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;init();cin>>t;while(t--) solve();
}

1007	Expectation (Easy Version)

直接枚举即可

当前i 贡献是i^m,概率是n场里面选择i场赢，赢i场的概率*输(n-i)场的概率

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;int n;
int a[N],b[N];
int fact[N],infact[N];
int qmi(int a, int k, int p)  // 求a^k mod p
{int res = 1 % p;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}void init(){fact[0] = infact[0] = 1;for (int i = 1; i < N; i ++ ){fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;}
}
int C(int a,int b){if(b>a) return 0;return ((LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
int gcd(int a, int b)  // 欧几里得算法
{return b ? gcd(b, a % b) : a;
}
void solve(){int n,m,x,y;cin>>n>>m>>x>>y;int win=x*qmi(y,mod-2,mod)%mod;int sum=0,ans=0;a[0]=b[0]=1;for(int i=1;i<=n;i++) a[i]=a[i-1]*win%mod;for(int i=1;i<=n;i++) b[i]=b[i-1]*(1-win+mod)%mod;for(int i=1;i<=n;i++){sum=(sum+qmi(i,m,mod))%mod;int res=C(n,i)*a[i]%mod*b[n-i]%mod*sum%mod;ans=(ans+res)%mod;}cout<<(ans+mod)%mod<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;init();cin>>t;while(t--) solve();
}

1003	String Magic (Easy Version)

对于每个下标 用合法的起点减去不合法的终点就是答案了，注释在代码里

要用到马拉车算法，求出f[ ]数组就是以i为中心的回文字符串的长度

每个字符串对应一个

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;typedef long long LL;
typedef pair<int, int> PII;
int n;
char ss[N];
int f[N];
int sum[N];
vector<int> V[N];
int tr[N];
int lowbit(int x)
{return x & -x;
}void add(int x, int c)  // 位置x加c
{while(x){tr[x]+=c;x-=lowbit(x);}
}int query(int x)  // 返回前x个数的和
{int res = 0;while(x<=n+n){res+=tr[x];x+=lowbit(x);}return res;
}void solve(){int ans=0;string s;cin>>s;n=s.size();s="?"+s;ss[0]='?';ss[n+n+2]='^';for(int i=1;i<=n;++i){ss[i+i-1]='*';ss[i+i]=s[i];ss[i+i+1]='*';}for(int i=1;i<=n+n;++i) V[i].clear(),tr[i]=0,f[i]=0;int mr=0,mid=0;for(int i=1;ss[i]!='^';i++){if(i<mr) f[i]=min(mr-i,f[2*mid-i]);else f[i]=1;while(ss[i+f[i]]==ss[i-f[i]]) f[i]++;if(f[i]+i>mr){mr=f[i]+i;mid=i;}}for(int i=1;i<=n+n;i++) f[i]--;//f[i]是求每个点为中心的最长回文串的长度for(int i=3;i<=n+n;++i){if(i%2==0)  continue;V[i-1].push_back(i);//有个性质*号的位置如果长度不是1，那么他对应的字符串长度一定是偶数//不是*号的字母回文字符一定包含*号 *a* 所以这是合法对数的起点V[i-(f[i]+1)/2-1].push_back(-i);//i-(f[i]+1)/2-1 的点就已经不在i的回文范围内了}for(int i=1;i<=n+n;++i){add(i+f[i],1);//当前i能扩展到右边的端点位置for(auto v:V[i]){if(v>0) ans+=query(v);else    ans-=query(-v);//相当于起点减去终点}}cout<<ans<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}