NOIP 2020
xjb乱做
时间：7:30~9:50
分数：100+80+0+40
T1 [NOIP2020] 排水系统
根据题目所给信息 有若干点没有出度 有若干点没有入度 且图不成环
一眼拓扑 直接做就可以了
(感觉应该不会炸long long罢 但为了保险起见仍然用的__int128)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
const int maxn=2e5+10;
const int INF=0x3f3f3f3f;
int n,m,deg[maxn],vis[maxn],pt[maxn];
vector<int>g[maxn];
pair<__int128,__int128>ans[maxn];
vector<pair<__int128,__int128>>init[maxn];
__int128 gcd(__int128 x,__int128 y){
if(y==0)return x;
return gcd(y,x%y);
}
void solve(int x){
if(x<=m)ans[x]={1,1};
else{
__int128 l=0,r=1;
for(auto k:init[x])r=r/gcd(r,k.second)*k.second;
for(auto k:init[x])l=l+r/k.second*k.first;
__int128 g=gcd(l,r);
l/=g,r/=g;
init[x].clear();
ans[x]={l,r};
}
}
void out(__int128 x,__int128 y){
int sta[50],tot=0;
while(x)sta[++tot]=x%10,x/=10;
for(int i=tot;i>=1;i--)cout<<sta[i];
cout<<" ";
tot=0;
while(y)sta[++tot]=y%10,y/=10;
for(int i=tot;i>=1;i--)cout<<sta[i];
cout<<"\n";
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
int num;cin>>num;
if(num==0)vis[i]=1;
pt[i]=num;
for(int j=1;j<=num;j++){
int x;cin>>x;
g[i].push_back(x);
deg[x]++;
}
}
queue<int>q;
for(int i=1;i<=m;i++)q.push(i);
while(q.size()){
int x=q.front();q.pop();
solve(x);
for(auto k:g[x]){
deg[k]--;
__int128 l=ans[x].first;
__int128 r=ans[x].second;
r=r*pt[x];
__int128 g=gcd(l,r);
l/=g,r/=g;
init[k].push_back({l,r});
if(!deg[k])q.push(k);
}
}
for(int i=1;i<=n;i++)if(vis[i])out(ans[i].first,ans[i].second);
return 0;
}
T2 [NOIP2020] 字符串匹配
数组开小了喜得80
观察题目性质 发现对于\(S=(AB)^iC\)而言 \(AB\)是定然在字符串开头的
这启示我们去枚举字符串\(AB\)的长度 枚举长度\(len\)之后 我们可以得到最大连续相同\(AB\)的个数
根据调和级，\(\sum_{i=1}^{n} \frac{n}{i}\)近似为\(nlog_en\) 所以可行
假设现在枚举了长度\(len\) 考虑\(C\)字符串的个数
对于每一个匹配上的地方 其后缀都可以作为\(C\) 看起来较为麻烦 但稍加分析可以得到不同的\(f(C)\)仅只有两种取值
这是因为\(C\)字符串在开头增加字符时 一定增加的是字符串\(AB\) 而\(f(C)\)的实际含义就是\(C\)中每个字符的异或之和
于是\(f(C)\)仅有两种取值 现在仅需知道有哪些\(f(A)\)小于等于\(f(C)\)即可
\(A\)一定为字符串的前缀 于是可以\(O(n)\)预处理出来\(f\) 然后前缀和查询即可
时间复杂度\(O(nlog_en+26n)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e6+10;
const int INF=0x3f3f3f3f;
int t,len;
char a[maxn];
int pre[maxn],suf[maxn],tong[30],sum[maxn][30],Hash[maxn],pw[maxn];
void init(){
int ans=0;
pw[0]=1;
for(int i=1;i<=len;i++){
Hash[i]=Hash[i-1]*131+a[i]-'a'+1;
pw[i]=pw[i-1]*131;
int x=a[i]-'a'+1;
ans-=tong[x];tong[x]^=1;
ans+=tong[x];
pre[i]=ans;
}
for(int i=1;i<=26;i++)tong[i]=0;
ans=0;
for(int i=len;i>=1;i--){
int x=a[i]-'a'+1;
ans-=tong[x];tong[x]^=1;
ans+=tong[x];
suf[i]=ans;
}
for(int i=1;i<=len;i++){
for(int j=0;j<=26;j++)sum[i][j]=sum[i-1][j];
for(int j=pre[i];j<=26;j++)sum[i][j]++;
}
for(int i=1;i<=26;i++)tong[i]=0;
}
int ans;
void solve(int l,int ed){
if(sum[l-1][suf[ed]]){
// cout<<ed<<" "<<suf[ed]<<endl;
ans=ans+sum[l-1][suf[ed]]*((ed-1-l)/(2*l)+1);
}
ed-=l;
if(ed>l){
if(sum[l-1][suf[ed]])ans=ans+sum[l-1][suf[ed]]*((ed-1-l)/(2*l)+1);
}
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>a+1;
len=strlen(a+1);
init();
// for(int i=1;i<=len;i++)cout<<pre[i];
// cout<<endl;
// for(int i=len;i>=1;i--)cout<<suf[i];
// cout<<endl;
ans=0;
for(int l=2;l<=len;l++){
int ed=0;
for(int j=l;j<=len;j+=l){
if(Hash[j]-Hash[j-l]*pw[l]!=Hash[l]){
ed=j-l+1;
break;
}
}
if(ed==0)ed=len/l*l+1;
if(ed==len+1)ed-=l;
if(ed>l)solve(l,ed);
// cout<<l<<" "<<ans<<endl;
}
cout<<ans<<"\n";
for(int i=0;i<=len;i++){
pre[i]=suf[i]=Hash[i]=pw[i]=0;
for(int j=0;j<=26;j++)sum[i][j]=0;
}
}
return 0;
}
T3 [NOIP2020] 移球游戏
神仙构造 很有意思
具体参见：https://www.luogu.com.cn/blog/61120/solution-p7115
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int INF=0x3f3f3f3f;
int n,m,a[405][405],cnt[maxn],p[maxn];
int solve(int x,int y){
int val=0;
for(int i=1;i<=m;i++)val=val+(a[x][i]==y);
return val;
}
vector<pair<int,int> >ans;
void to(int x,int y){
ans.push_back({x,y});
a[y][++cnt[y]]=a[x][cnt[x]--];
}
void work(){
int siz=solve(p[1],1);
for(int i=m;i>m-siz;i--)to(p[2],p[3]);
for(int i=m;i>=1;i--){
if(a[p[1]][i]==1)to(p[1],p[2]);
else to(p[1],p[3]);
}
for(int i=m;i>m-siz;i--)to(p[2],p[1]);
for(int i=m;i>siz;i--)to(p[3],p[1]);
for(int i=siz;i>=1;i--)to(p[3],p[2]);
for(int i=m;i>siz;i--)to(p[1],p[3]);
for(int i=m;i>=1;i--){
if(a[p[2]][i]==1)to(p[2],p[1]);
else to(p[2],p[3]);
}
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cnt[i]=m;p[i]=i;
for(int j=1;j<=m;j++)cin>>a[i][j];
}
p[n+1]=n+1;
for(int i=n;i>=3;i--){
//全0
int siz=solve(p[1],i);
for(int j=m;j>m-siz;j--)to(p[i],p[i+1]);
for(int j=m;j>=1;j--){
if(a[p[1]][j]==i)to(p[1],p[i]);
else to(p[1],p[i+1]);
}
for(int j=m;j>siz;j--)to(p[i+1],p[1]);
for(int j=m;j>=1;j--){
if(a[p[2]][j]==i||cnt[p[1]]==m)to(p[2],p[i+1]);
else to(p[2],p[1]);
}
swap(p[1],p[i]),swap(p[2],p[i+1]);
//全1
for(int j=1;j<i;j++){
int siz=solve(p[j],i);
for(int k=m;k>m-siz;k--)to(p[i],p[i+1]);
for(int k=m;k>=1;k--){
if(a[p[j]][k]==i)to(p[j],p[i]);
else to(p[j],p[i+1]);
}
swap(p[j],p[i+1]);swap(p[j],p[i]);
}
//结束
for(int j=1;j<i;j++){
while(a[p[j]][cnt[p[j]]]==i)to(p[j],p[i+1]);
}
for(int j=1;j<i;j++){
while(cnt[p[j]]!=m)to(p[i],p[j]);
}
}
//n==2
work();
cout<<ans.size()<<"\n";
for(auto k:ans)cout<<k.first<<" "<<k.second<<"\n";
return 0;
}
T4 [NOIP2020] 微信步数
不难 思路较为自然
不妨将答案转化一下 求从每个位置出发走的步数之和其实就等于求每天还剩下的起点的个数
这里的起点专指刚开始所处于的位置
不妨先只考虑第一轮（\(n\)步算一轮）
对于每个维度 显然是互相独立的 分别考虑每个维度
那么我们可以求出每个维度往左的最大偏移量和往右的最大偏移量 令其为\(l_i,_j\)和\(r_i,_j\) 定义为在第一轮时走了\(i\)步后第\(j\)维的往左/右的最大偏移量
那么显然 在第一天过后还存在的点的个数为\(\prod_{i=1}^{m}w_i-(r_1,_i-l_1,_i)\) 同理可以扩展到\(2～n\)天
无解的判断条件也很简单 仅需判断在一轮之后总偏移量全为0且没有走出场地 这时候定然无解
下面考虑第二轮 直觉上 每一轮移动过后都存在一定的周期性 自然是对的
令\(sum_i\)为第\(i\)位在第一轮的总偏移量 只要\(sum_i\)不等于0 第二轮总会有点走出 令第一轮的偏移区间为边界 可以得到：
\[l'_i,_j=min(0,l_i,_j+sum_j-l_n,_j)\\
r'_i,_j=max(0,r_i,_j+sum_j-r_n,_j)
\]
其中\(l'_i,_j\)的定义为在上一轮的基础之上这一轮向左增加的偏移量 \(r'\)同理
因为每一轮做的操作相同 所以每一轮会走出的起点数是一样的 但是要特殊考虑第一轮 因为第一轮不依赖于任何一轮 我们把第一轮操作之后第\(i\)维还剩下的起点个数令为\(a_i\)
（如果\(n\)步走完之后还没有走出） 令其为\(b_i,_j=r'_i,_j-l'_i,_j\) 含义为在某一轮的第\(i\)步 第\(j\)维相对于上一轮多走出的起点数
那么有答案:
\(ans=\sum_{i=1}^{n}\sum_{x=0}^{T}\prod_{j=1}^{m} a_j-xb_j-(r'_i,_j-l'_i,_j)\) 其中\(T\)为最多轮数
考虑求出这个式子 对于\(\prod_{j=1}^{m}a_j-xb_j-(r'_i,_j-l'_i,_j)\) 可以直接暴力拆多项式得到一个最高次数为\(m\)的多项式子，令其为\(p_0x^0+p_1x^1+...p_mx^m\)
那么将外围的\(\sum_{x=0}^{T}\)拆开 即求：\(p_i(\sum_{x=0}^{T}x^i)\)
对于\(\sum_{x=0}^{T}x^i\)的求解 这个式子的和为一个关于\(T\)的\(i+1\)次多项式 即仅需要\(i+2\)个点就可以通过拉格朗日插值得到这个多项式 取连续的\(i+2\)个点即可\(O(k)\)求解
总复杂度\(O(nk^2)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int limit=1e6;
int n,m,w[maxn],c[maxn],d[maxn],fac[maxn],l[maxn][11],r[maxn][11],sum[maxn];
int ans,a[maxn],b[maxn];
int qpow(int x,int y){
int val=1;
while(y){
if(y&1)val=val*x%mod;
x=x*x%mod,y/=2;
}
return val;
}
void solve1(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)l[i][j]=l[i-1][j],r[i][j]=r[i-1][j];
sum[c[i]]+=d[i];
l[i][c[i]]=min(l[i][c[i]],sum[c[i]]);
r[i][c[i]]=max(r[i][c[i]],sum[c[i]]);
int val=1;
for(int j=1;j<=m;j++)val=val*(max((int)0,w[j]-r[i][j]+l[i][j]))%mod;
ans=(ans+val)%mod;
}
int siz=0;
for(int i=1;i<=m;i++){
if(sum[i]==0&&l[n][i]<=r[n][i])siz++;
}
if(siz==m){
cout<<-1;
exit(0);
}
for(int i=1;i<=m;i++)a[i]=w[i]-r[n][i]+l[n][i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
l[i][j]=min((int)0,l[i][j]+sum[j]-l[n][j]);
r[i][j]=max((int)0,r[i][j]+sum[j]-r[n][j]);
}
}
for(int i=1;i<=m;i++)b[i]=r[n][i]-l[n][i];
}
int f[15][15];//多项式系数
int v[maxn];//k次方之和
//拉格朗日
int Y[maxn],pre[maxn],suf[maxn];
int get_(int x,int k){
pre[0]=suf[k+3]=1;
int val=0;
for(int i=1;i<=k+2;i++)pre[i]=pre[i-1]*(x-i+mod)%mod;
for(int i=k+2;i>=1;i--)suf[i]=suf[i+1]*(x-i+mod)%mod;
for(int i=1;i<=k+2;i++){
int ls=pre[i-1]*suf[i+1]%mod;
int rs=fac[i-1]*fac[k+2-i]%mod;
if((k+2-i)%2)rs=(mod-rs);
val=(val+Y[i]*ls%mod*qpow(rs,mod-2)%mod)%mod;
}
return val;
}
int work(int x,int k){
for(int i=1;i<=k+2;i++)Y[i]=(Y[i-1]+qpow(i,k))%mod;
return get_(x,k);
}
void solve(){
int lst=-1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++)f[0][j]=0;
int t=INF;
f[0][0]=1;
for(int j=1;j<=m;j++){
int val=a[j]-(r[i][j]-l[i][j]);
if(val<=0)return ;
if(b[j]>0)t=min(t,val/b[j]);
for(int k=0;k<=m;k++){
f[j][k]=f[j-1][k]*val%mod;
if(k)f[j][k]=(f[j][k]+f[j-1][k-1]*(-b[j])%mod+mod)%mod;
}
}
ans=(ans+f[m][0]*(t+1)%mod)%mod;
if(t!=lst){
lst=t;
for(int j=1;j<=m;j++)v[j]=work(t,j);
}
for(int j=1;j<=m;j++)ans=(ans+v[j]*f[m][j]%mod)%mod;
}
}
//草履虫大胜利！
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
fac[0]=1;
for(int i=1;i<=limit;i++)fac[i]=fac[i-1]*i%mod;
ans=1;
for(int i=1;i<=m;i++)cin>>w[i],ans=ans*w[i]%mod;
for(int i=1;i<=n;i++)cin>>c[i]>>d[i];
solve1();
solve();
cout<<ans;
return 0;
}
草履虫胜利了！！！！！！！