首页 > 其他分享 >NOIP 2020

NOIP 2020

时间：2023-10-26 21:36:13浏览次数：47  
标签：const NOIP int sum -- maxn ans 2020

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;
}

草履虫胜利了！！！！！！！

标签：const,NOIP,int,sum,--,maxn,ans,2020
From： https://www.cnblogs.com/c20230507/p/17790443.html

相关文章

  • 20231019NOIP训练赛
    20231019NOIP训练赛时间安排7:50-8:50写T18:50-9:30写T29:30-10:30写T3T410:30-11:50写T1总结T2没花时间想，没想到建图题解T1枚举最大公约数，然后统计最大公约数的倍数T2并查集，设u=\(X_{b_i}\)，v=\(X_{a_i}\)，在u和v间建一条长度为\(c_i\)的边，可以用并查集维护，如果u和v已......
  • NOIP2023模拟2联测23 T2 害怕
    NOIP2023模拟2联测23T2害怕好像写了一种出题人意料之外的算法。思路在生成树上加入白边，白边和若干条蓝色边形成环，环上的蓝色边必须要分配比该白色边更小的边权（最小生成树）。给每一条边一个分配优先级，优先级的数越小，优先级越高，分配的边权越小。一开始所有边的优先级的数都等......
  • NOIP2023模拟2联测23 C. 负责
    NOIP2023模拟2联测23C.负责目录NOIP2023模拟2联测23C.负责题目大意思路code题目大意给你\(n\)个区间\([l_i,r_i]\)，每个区间有个\(w_i\)。如果两个区间有交集（包括端点）那么两个区间就可以连边，形成一个图。现在需要你删除一些区间，使得每个区间大小不超过\(k\)。......
  • 考场（NOIP2023模拟2联测23）
    T1一眼顶针鉴定不出来，二眼顶针看出来是贪心，对于一个序列来说肯定要选值小的数来拉低平均数，鉴定完毕T2有点东西，也许是要用\(kruskal\)或\(prim\)的思想做题？？？边从前向后遍历，若一个边不是树边，因为要保证树边权最小，所以每次要更新树边的边权，然后再更新非树边边权，更新树边边权时......
  • 【洛谷 2347】[NOIP1996 提高组] 砝码称重
    题目描述设有 1g1g、2g2g、3g3g、5g5g、10g10g、20g20g 的砝码各若干枚（其总重≤1000≤1000），可以表示成多少种重量？输入格式输入方式：�1,�2,�3,�4,�5,�6a1​,a2​,a3​,a4​,a5​,a6​（表示 1g1g 砝码有 �1a1​ 个，2g2g 砝码有 �2a2​ 个，…，20g20g 砝码有 �6a6​ 个）输出格式......
  • NOIP冲刺之超市T2计划
    超市T2计划总结目录超市T2计划总结声明：刷题：三国游戏：T1尼克的任务：T2卖萝卜：T1剔除多余括号：T2引水入城：T3MediumDesign:T3总结：声明：本贴用于总结对于csps-noipT2左右难度的题目。会选择一些NOIP的题目，或者是codeforces过的人数在1500~3000的题目。然后分为了T1-T66个级别也......
  • 2023NOIP A层联测16 T3 货物运输
    2023NOIPA层联测16T3货物运输题目描述说这是一个仙人掌图，通常将问题转换为环和树的问题在使用圆方树来解决。树解法令\(a_i=s_i-\frac{\sums_i}{n}\)，最终令\(a_i=0\)。通过树形dp，从叶子节点向上转移，叶子节点要么向父亲拿资源，要么向父亲传资源，所以转移为：\[a_{fa}+=a_i......
  • P2679 [NOIP2015 提高组] 子串 题解
    #include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintMOD=1000000007;intn,m,k,dp[205][205][2];charA[1005],B[205];signedmain(){cin.tie(0)->sync_with_stdio(0);cin>>n>>m>>k;cin......
  • NOIP模拟赛记录
    NOIP模拟赛记录2023.10.23比赛记录A.公园直接dijkstra即可可爱的code捏#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineullunsignedlonglong#defineALL(a)(a).begin(),(a).end()#definepbpush_back#definemkmake_pair#defin......
  • 软考系列（系统架构师）- 2020年系统架构师软考案例分析考点
    试题一软件架构（架构风格、质量属性）【问题1】（13分）针对该系统的功能，李工建议采用管道-过滤器（pipeandfilter)的架构风格，而王工则建议采用仓库（reposilory)架构风格。请指出该系统更适合采用哪种架构风格，并针对系统的主要功能，从数据处理方式、系统的可扩展性和处理性能三个方面对......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99