2023 (ICPC) Jiangxi Provincial Contest -- Official Contest
思路:n>=s*v
思路:对a进行a%m,不会对结果造成影响,则0<=bi+1-bi<m。可以求bi+1%m<bi%m的个数,等价于bi+1/m>bi/m,整体来看,就是求bn/m
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; #define int long long int k,n,m,x,ans=0; int a[N],b[N],all=0; void solve(){ cin>>k; for(int i=1;i<=k;++i){ cin>>a[i]; } cin>>n>>m>>x;x%=m; for(int i=1;i<=k;++i){ a[i]%=m; all+=a[i]; } int c=ceil(1.0*n/k)-1,s=n-c*k; b[1]=x+c*all+a[1]; for(int i=2;i<=s;++i){ b[i]=a[i]+b[i-1]; } ans=n-(b[s]/m); cout<<ans; } int32_t main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
思路:用f[i]维护所有到i点的边的边权异或和,对于修改操作x→y,可以看出x→y中除了x和y以外的点的f不变,修改x和y点的f即可
#include<bits/stdc++.h> using namespace std; int f[500005]; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,k; cin>>n>>k; for (int i = 0; i < n-1; ++i) { int x,y,z; cin>>x>>y>>z; f[x]^=z; f[y]^=z; } while(k--){ int op; cin>>op; if(op==2){ int x; cin>>x; cout<<f[x]<<'\n'; } else{ int x,y,z; cin>>x>>y>>z; f[x]^=z,f[y]^=z; } } }
思路:由于a,b小于等于n,当询问x=c时,经过x=c的函数f在x=c±√n范围内,枚举每一个范围内的f即可(当y=n,b=1(极限)时,n=(x-a)2+1,可知x在±√n内的函数可达到x=a;对于增加操作,由于询问只求最小的函数值,维护每个a(x)的最小b即可
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; //#define int long long int n,c[N]; void solve(){ cin>>n; for(int i=1;i<=n;++i)cin>>c[i]; int m; cin>>m; int s= ::sqrt(1.0*n); while(m--){ int op,a,b; cin>>op; if(op){ cin>>a; int ans=INF; for(int i=0;i<=s;++i){ int l=a-i,r=a+i; if(l>0&&c[l])ans=min(ans,(a-l)*(a-l)+c[l]); if(r<=n&&c[r])ans=min(ans,(a-r)*(a-r)+c[r]); } cout<<ans<<'\n'; } else{ cin>>a>>b; c[a]=min(c[a],b); } } } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
思路:序列是不递增的,分成k段,每个分段点i对答案的贡献为a[i+1]-a[i],那么求出差分,找出前k-1个即可
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; //#define int long long int n,a[N],b[N]; void solve(){ cin>>n; for(int i=0;i<n;++i){ cin>>a[i]; if(i)b[i]=a[i]-a[i-1]; } sort(b+1,b+n); for(int i=1;i<n;++i){ b[i]+=b[i-1];//cout<<b[i]<<' '; }//cout<<'\n'; int m; cin>>m; while(m--){ int op,x; cin>>op>>x; if(op==1){ cout<<a[0]-a[n-1]+b[x-1]<<'\n'; } } } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
L - Zhang Fei Threading Needles - Thick with Fine
思路:n-1
- Contest Provincial Official Jiangxi 2023contest provincial official jiangxi contest 2023 provincial official programming collegiate provincial contest programming provincial contest shaanxi 2019 programming provincial contest 2023 programming collegiate provincial jiangxi official contest summer round 2023 regionals contest online 2023