先写实验报告,回来再补文字题解
1计算括号对
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) typedef double db; typedef long long ll; struct cp { db x,y; cp(db real=0,db imag=0):x(real),y(imag){}; cp operator +(cp b)const{return {x+b.x,y+b.y};} cp operator -(cp b)const{return {x-b.x,y-b.y};} cp operator*(cp b)const{return {x*b.x-y*b.y,x*b.y+y*b.x};} }; using vcp=vector<cp>; using Poly=vector<int>; class Cipolla { int P,I2{}; using pll=pair<ll,ll>; }; #define MUL(a,b) (ll(a)*(b)%P) #define ADD(a,b) (((a)+=(b))>=P?(a)-=P:0) #define SUB(a,b) (((a)-=(b))<0?9a)+=P:0) const int P=1e9+7,N=2e5+10; Poly getINV(int L){ Poly inv(L);inv[1]=1; rep(i,2,L-1) inv[i]=MUL((P-P/i),inv[P%i]);return inv; } int POW(ll a,int b=P-2,ll x=1) { for(;b;b>>=1,a=a*a%P) if(b&1)x=x*a%P; return x; } //auto inv=getInv(N); namespace FFT{ const db pi=acos(-1); vcp Omega(int L){ vcp w(L);w[1]=1; for(int i=2;i<L;i<<=1){ auto w0=w.begin()+i/2,w1=w.begin()+i; cp wn(cos(pi/i),sin(pi/i)); for(int j=0;j<i;j+=2) w1[j]=w0[j>>1],w1[j+1]=w1[j]*wn; } return w ; } auto W=Omega(1<<19); void DIF(cp *a,int n){ cp x,y; for(int k=n>>1;k;k>>=1) for(int i=0;i<n;i+=k<<1) for(int j=0;j<k;j++) x=a[i+j],y=a[i+j+k],a[i+j+k]=(a[i+j]-y)*W[k+j],a[i+j]=x+y; } void IDIT(cp *a,int n){ cp x,y; for(int k=1;k<n;k<<=1) for(int i=0;i<n;i+=k<<1) for(int j=0;j<k;j++) x=a[i+j],y=a[i+j+k]*W[k+j],a[i+j+k]=x-y,a[i+j]=x+y; const db Inv=1. /n; rep(i,0,n-1)a[i].x*=Inv,a[i].y*=Inv; reverse(a+1,a+n); } } namespace Polynomial{ void DFT(vcp &a){FFT::DIF(a.data(),a.size());} void IDFT(vcp &a){FFT::IDIT(a.data(),a.size());} int norm(int n){return 1<<(__lg(n-1)+1);} void norm(Poly &a){if(!a.empty())a.resize(norm(a.size()),0); else a={0};} vcp &dot(vcp &a,vcp &b){rep(i,0,a.size()-1)a[i]=a[i]*b[i]; return a;} Poly operator *(ll k,Poly a){ Poly ans; for(auto i:a) ans.push_back(k*i); return ans; } Poly operator *(Poly a,Poly b){ int n=a.size()+b.size()-1; vcp c(norm(n)); rep(i,0,a.size()-1)c[i].x=a[i]; rep(i,0,b.size()-1)c[i].y=b[i]; DFT(c),dot(c,c),IDFT(c),a.resize(n); rep(i,0,n-1)a[i]=(int)(c[i].y*.5+.5); return a; } } using namespace Polynomial; char s[N]; int n; int main() { // freopen("1.in","r",stdin); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>s+1; n=strlen(s+1)+10; int m=strlen(s+1); Poly vec1(n),vec2(n); for(int i=1;i<=m;i++) { if(s[i]=='(') vec1[m-i]=1; else vec2[i]=1; } Poly ans=vec1*vec2; // for(auto x:vec1) cout<<x<<" "; // cout<<endl; // for(auto x:vec2) cout<<x<<" "; // cout<<endl; // for(int i=0;i<vec1.size();i++) cout<<vec1[i]<<" "; // cout<<endl; // for(int i=0;i<vec2.size();i++) cout<<vec2[i]<<" "; // cout<<endl; // for(auto x: ans) cout<<x<<" "; // cout<<endl; bool flag=true; for(int i=1;i<m;i++) { if(flag) flag=false; else cout<<" "; cout<<ans[i+m]; } cout<<endl; // cout<<(1<<18)<<endl; return 0; }1
3最大的数
#include<bits/stdc++.h> using namespace std; typedef long long ll; int read() { int x;scanf("%d",&x);return x; } int n,b[200010],ans[20]; vector<int>e[200010],pos[200010],can[20]; int main() { n=read(); for(int i=1;i<=n;i++) e[i].push_back(read()); for(int i=1;i<=n;i++) { b[i]=read(); pos[b[i]].push_back(i); } for(int i=9;i>=0;i--) { if(pos[i].size()) { ans[1]=i; can[1]=pos[i]; break; } } for(int i=1;i<=8;i++) { for(auto po:can[i]) { for(auto y:e[po]) ans[i+1]=max(ans[i+1],b[y]); } for(auto po:can[i]) { for(auto y:e[po]) if(b[y]==ans[i+1]) can[i+1].push_back(y); } cout<<ans[i]; } cout<<ans[9]; }View Code
4兔子爱吃胡萝卜
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int N=1010; int f[N][N]; int a[N]; int n,m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=m;i++) cin>>a[i],a[i]%=n; f[1][a[1]]=1; for(int i=2;i<=m;i++) { f[i][a[i]]=1; for(int j=0;j<n;j++) { f[i][(j+a[i])%n]|=f[i-1][j]; f[i][j]|=f[i-1][j]; } } // for(int i=1;i<=m;i++) // { // for(int j=0;j<n;j++) // { // cout<<f[i][j]<<" "; // } // cout<<endl; // } if(f[m][0]) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }View Code
5小Z的难题
#include<bits/stdc++.h> using namespace std; typedef long long ll; int read() { int x;scanf("%d",&x);return x; } int n; char s[200010]; int check() { for(int i=0;i<n;i++) if(s[i]!='z') return 0; return 1; } int main() { n=read(); scanf("%s",s); if(check()) printf("No solution"); else { s[n-1]++; n--; while(s[n]=='z'+1) { s[n]='a'; n--; s[n]++; } printf("%s",s); } }View Code
6莫比乌斯最大值isUsefulAlgorithm
#include<bits/stdc++.h> using namespace std; typedef long long ll; int read() { int x;scanf("%d",&x);return x; } int n,a[100010],b[100010]; ll ans; int main() { n=read(); for(int i=1;i<=n;i++) a[read()]=1; for(int j=1;j<=n;j++) b[read()]=1; for(int i=1;i<=100000;i++) { ll maxa=0,maxb=0; for(int j=i;j<=100000;j+=i) { if(a[j]) maxa=j; if(b[j]) maxb=j; } ans=max(ans,maxa*maxb*i); } cout<<ans; }View Code
7爆米花
#include<bits/stdc++.h> using namespace std; typedef long long ll; int read() { int x;scanf("%d",&x);return x; } ll n; int main() { n=read(); cout<<(1+n)*n/2-n+1; }View Code
8what's 莫比乌斯最大值
#include<bits/stdc++.h> using namespace std; typedef long long ll; int read() { int x;scanf("%d",&x);return x; } int n,flag[1010],len[1010],ans; ll f[1010][1010]; string s[1010]; ll B=233,M=1e9+7; map<ll,int>o; void work(int i) { f[i][0]=s[i][0]; for(int j=1;j<len[i];j++) f[i][j]=(f[i][j-1]*B+s[i][j])%M; } int main() { // freopen("1.in","r",stdin); cin>>n; getline(cin,s[0]); for(int i=1;i<=n;i++) getline(cin,s[i]); for(int i=1;i<=n;i++) { if(s[i].substr(0,7)=="what's ") { s[i]=s[i].substr(7,s[i].length()-7); flag[i]=1; len[i]=s[i].length(); work(i); } else { len[i]=s[i].length(); work(i); int pos=0; for(int j=1;j<i;j++) { // cout<<"??"; if(flag[j]&&len[i]>=len[j]&&f[j][len[j]-1]==f[i][len[j]-1]&&len[j]>len[pos]&&o[f[j][len[j]-1]]==0) pos=j; } if(pos!=0) { ans++; flag[pos]=0; o[f[pos][len[pos]-1]]=1; } } } cout<<ans; }View Code
10售卖车票
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int N=6e5+10; struct node { int l,r; bool operator<(const node &a) { return l<a.l; } }p[N]; ll c[N]; int n,m,k; void add(int x,int y) { for(;x<=n;x+=x&-x) { c[x]+=y; } } ll ask(int x) { ll ans=0; for(;x;x-=x&-x) { ans+=c[x]; } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>k; for(int i=1;i<=m;i++) { cin>>p[i].l>>p[i].r; } sort(p+1,p+m+1); int t=1; priority_queue<pair<int,int>> q; for(int i=1;i<=n;i++) { while(t<=m&&p[t].l<=i) { int l=p[t].l; int r=p[t].r; add(l,1); add(r+1,-1); q.push({r,l}); t++; } int z=ask(i); if(z>k) { while(z>k) { auto it=q.top(); q.pop(); int l=it.second; int r=it.first; add(l,-1); add(r+1,1); z--; } } } // while(q.size()) // { // cout<<q.top().first<<" "<<q.top().second<<endl; // q.pop(); // } cout<<q.size()<<endl; return 0; }View Code
11Alice and Bob
#include<bits/stdc++.h> using namespace std; typedef long long ll; int read() { int x;scanf("%d",&x);return x; } char x[3][100010],y[3][100010]; int d[10]; int check(int t) { if(strlen(x[t])>6||strlen(y[t])>6) return 1;//chu ba ll xx=0,yy=0; for(int i=x[t][0]=='-'?1:0;i<strlen(x[t]);i++) xx=xx*10+x[t][i]-'0'; for(int i=y[t][0]=='-'?1:0;i<strlen(y[t]);i++) yy=yy*10+y[t][i]-'0'; d[t]=xx*xx+yy*yy; return d[t]>1000000; } int main() { scanf("%s%s",x[1],y[1]); scanf("%s%s",x[2],y[2]); if(check(1)&&check(2)) printf("Draw"); else if(check(1)) printf("Bob"); else if(check(2)) printf("Alice"); else { if(d[1]==d[2]) printf("Draw"); else if(d[1]<d[2]) printf("Alice"); else printf("Bob"); } }View Code
12子序列
#include<bits/stdc++.h> using namespace std; typedef long long ll; int read() { int x;scanf("%d",&x);return x; } ll n,a[300010],b[300010],sum[300010],m,ni[300010]; ll inv[300010],fac[300010],mod=998244353; ll t=1,tsum,tt; ll quick(ll x,ll y) { ll t=1; while(y) { if(y&1) t=t*x%mod; x=x*x%mod; y=y/2; } return t; } ll C(ll b,ll a) { return fac[a]*inv[b]%mod*inv[a-b]%mod; } ll work() { ll ans=0; for(int i=1;i<=m;i++) { if(sum[i]>=2) { tt=(tt-C(2,sum[i])*ni[(sum[i]+1)]%mod*C(2,sum[i])%mod*ni[(sum[i]+1)]%mod)%mod; tsum=(tsum-C(2,sum[i])*ni[(sum[i]+1)]%mod)%mod; tt=(tt+mod)%mod; tsum=(tsum+mod)%mod; ans=(ans+C(2,sum[i])*ni[sum[i]+1]%mod*((tsum*tsum%mod-tt)%mod+mod)%mod)%mod; tt=(tt+C(2,sum[i])*ni[(sum[i]+1)]%mod*C(2,sum[i])%mod*ni[(sum[i]+1)]%mod)%mod; tsum=(tsum+C(2,sum[i])*ni[(sum[i]+1)]%mod)%mod; } } ans=ans*t%mod*ni[6]%mod; return (ans+mod)%mod; } int main() { ll ans=0; // freopen("1.in","r",stdin); n=read(); for(int i=1;i<=n;i++) b[i]=a[i]=read(); sort(b+1,b+1+n); m=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++) sum[lower_bound(b+1,b+1+m,a[i])-b]++; fac[0]=inv[0]=1; for(int i=1;i<=200010;i++) fac[i]=fac[i-1]*i%mod; inv[200010]=quick(fac[200010],mod-2); for(int i=200010;i>=1;i--) inv[i-1]=inv[i]*i%mod; for(int i=1;i<=200010;i++) ni[i]=quick(i,mod-2); for(int i=1;i<=m;i++) t=t*(sum[i]+1)%mod; for(int i=1;i<=m;i++) if(sum[i]>=2) tsum=(tsum+C(2,sum[i])*ni[(sum[i]+1)]%mod)%mod; for(int i=1;i<=m;i++) if(sum[i]>=2) tt=(tt+C(2,sum[i])*ni[(sum[i]+1)]%mod*C(2,sum[i])%mod*ni[(sum[i]+1)]%mod)%mod; ans=(ans+t*(tsum*tsum%mod-tt)%mod)%mod; ans=(ans+mod)%mod; ans=ans*ni[2]%mod; for(int i=1;i<=m;i++) if(sum[i]>=2) ans=(ans+C(2,sum[i])*ni[(sum[i]+1)]%mod*t%mod)%mod; ans=(ans+t-1)%mod; for(int i=1;i<=m;i++) if(sum[i]>=3) ans=(ans+C(3,sum[i])*t%mod*ni[sum[i]+1]%mod)%mod; ans=ans+work(); cout<<ans%mod<<endl; }View Code
标签:int,ll,long,sum,ans,卓见,第十五届,邀请赛,mod From: https://www.cnblogs.com/qywyt/p/17281504.html