臺州學院ICPC賽前訓練5

人生第一次ak，而且ak得還蠻快的，感謝隊友帶我飛

A 直接用claris的模板啊，他模板確實比較強大，其實就是因為更新的很快

#include<bits/stdc++.h> using namespace std; int fun(int x,int y) {return x&y; } const int N=1e5+5; int n,a[N],l[N],v[N]; int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T;cin>>T;while(T--){cin>>n;for(int i=1; i<=n; i++)cin>>a[i];long long ans=0;for(int i=1,j; i<=n; i++)for(v[i]=a[i],j=l[i]=i; j; j=l[j]-1){v[j]=fun(v[j],a[i]);while(l[j]>1&&fun(a[i],v[l[j]-1])==fun(a[i],v[j]))l[j]=l[l[j]-1];ans+=v[j]*1LL*(j-l[j]+1);}cout<<ans<<"\n";}return 0; } View Code

B按照題意寫就好了

#include<bits/stdc++.h> using namespace std;int a[1005]; int main() {int t;scanf("%d",&t);while(t--){int n,m,tian=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==-1)tian++;}if(tian==n){a[1]=0;printf("%d",a[1]);for(int i=2;i<=n;i++){a[i]=(a[i-1]+1)%m;printf(" %d",a[i]);}printf("\n");continue;}for(int i=1;i<=n;i++){if(a[i]!=-1){for(int j=i+1;j<=n;j++){if(a[j]==-1){a[j]=(a[j-1]+1)%m;}elsebreak;}}}for(int i=1;i<=n;i++){if(a[i]!=-1){for(int j=i-1;j>=1;j--){if(a[j]==-1)a[j]=(a[j+1]-1+m)%m;}}}printf("%d",a[1]);for(int i=2;i<=n;i++)printf(" %d",a[i]);printf("\n");}return 0; } View Code

C隊友貌似寫了很久的感覺，用了二分

#include <bits/stdc++.h> using namespace std; const int MD=1e9+7; int a[100005],b[100005],n; int calc(int x) {int l=0,r=n-1,ans=-1;while(l<=r){int mid=(l+r)>>1;if(b[mid]<=x) ans=mid,l=mid+1;else r=mid-1;}return ans; } int main() {int T;scanf("%d",&T);while(T--){map<int,int> ma;scanf("%d",&n);int maxx=-1,maxxx=-1;for(int i=0;i<n;i++){scanf("%d",&a[i]);b[i]=a[i];if(maxx<a[i]) maxxx=maxx,maxx=a[i];else if(maxxx<a[i]) maxxx=a[i];ma[a[i]]++;}sort(b,b+n);for(int i=0;i<n;i++){int tmp=MD-a[i]-1,ans=calc(tmp);if(ans==-1){if(a[i]==maxx&&ma[maxx]==1) a[i]=(a[i]+maxxx)%MD;else a[i]=(a[i]+maxx)%MD;}else {if(b[ans]!=a[i]) a[i]=(a[i]+b[ans])%MD;else {if(ans==0) a[i]=(a[i]+maxx)%MD;else a[i]=(a[i]+b[ans-1])%MD;}}}for(int i=0;i<n;i++)printf("%d%c",a[i],i==n-1?'\n':' ');}return 0; } View Code

D就是分循環節，要找到左端點和右端點

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; char s[N]; int pre[N][30],lst[N][30]; int main() {int T;scanf("%d",&T);while(T--){int n,q;scanf("%d%d",&n,&q);getchar();scanf("%s",s+1);for(int i=1;i<=n;i++)for(int j=0;j<26;j++)pre[i][j]=pre[i-1][j]+(s[i]-'a'==j);for(int j=0;j<26;j++)lst[n][j]=(s[n]-'a'==j);for(int i=n-1;i>0;i--)for(int j=0;j<26;j++)lst[i][j]=lst[i+1][j]+(s[i]-'a'==j);while(q--){int l,r;char c;scanf("%d%d %c",&l,&r,&c);long long L=l/n*n,R=r/n*n;if(L<l)L+=n;//cout<<L<<" "<<R<<"\n";long long ans=0;ans=(R-L)/n*1LL*pre[n][c-'a'];ans+=lst[l%n==0?n:l%n][c-'a'];ans+=pre[r%n][c-'a'];cout<<ans<<"\n";}}return 0; } View Code

E折半搜索，寫的很爽，這個主要是這個復雜度大大降低

#include <bits/stdc++.h> using namespace std; const int MD=1e9+7; unordered_map<int,int>M; int po(int a,int x) {int ans=1;for(;x;a=a*1LL*a%MD,x>>=1)if(x&1)ans=ans*1LL*a%MD;return ans; } int a[20][10]; int n,k; long long ans; void dfs(int now,int tot,int lst,int sta) {if(tot==lst){if(sta)M[now]++;else{int t=k*1LL*po(now,MD-2)%MD;if(M.count(t))ans+=M[t];}return;}for(int i=0;i<6;i++)dfs(now*1LL*a[tot][i]%MD,tot+1,lst,sta); } int main() {int T;cin>>T;while(T--){cin>>n>>k;for(int i=0;i<n;i++)for(int j=0;j<6;j++)cin>>a[i][j];M.clear(),ans=0;dfs(1,0,n/2,1);dfs(1,n/2,n,0);cout<<ans<<"\n";}return 0; } View Code

F暴力判斷下回文，然后ST表二分就好了。注意是兩個字符串之間，所以l和r要swap

#include<bits/stdc++.h> using namespace std;const int maxn=1e4+100;int cnt[maxn],n,q; string s[maxn];const int level=30;struct ST{int Max[maxn][level];int build(){for(int i=1;i<=n;i++)Max[i][0]=cnt[i];for(int j=1;j<level;j++)for(int i=1;i+(1<<(j-1))<=n;i++){Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);}}int query(int l,int r){int k=log2(r-l+1.0);return max(Max[l][k],Max[r-(1<<k)+1][k]);} }T;inline bool check(int x,int l,int r) {int len=s[x].size(),mid=(l+r)/2;for(int i=l;i<=mid;i++)if(s[x][l++]!=s[x][r--])return false;return true; } int hw(int x) {int len=s[x].size(),cnt=0;for(int l=0;l<len;l++)for(int r=l;r<len;r++)if(check(x,l,r))cnt++;return cnt; }unordered_map<long long,int>ma; long long HASH(int x) {int len=s[x].size();long long sum=0;for(int i=0;i<len;i++)sum=sum*4+(s[x][i]-'a'+1);return sum; } int main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){ma.clear();cin>>n>>q;for(int i=1;i<=n;i++){cin>>s[i];cnt[i]=hw(i);//printf("%d\n",cnt[i]);ma[HASH(i)]=i;}T.build();for(int i=0;i<q;i++){cin>>s[n+1]>>s[n+2];int l=ma[HASH(n+1)],r=ma[HASH(n+2)];if(l>r)swap(l,r);int z=l,ans=l;int MAX=T.query(l,r);while(l<=r){int mid=(l+r)>>1;if(T.query(z,mid)==MAX){ans=mid;r=mid-1;}elsel=mid+1;}cout<<ans<<'\n';}}return 0; } View Code

G前綴和后綴找下最大最小值就好

#include<bits/stdc++.h> using namespace std;const int maxn=1e6+5; int MAX[maxn],MIN[maxn],a[maxn]; int main() {int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);MAX[1]=a[1];for(int i=2;i<=n;i++)MAX[i]=max(a[i],MAX[i-1]);MIN[n]=a[n];for(int i=n-1;i>=1;i--)MIN[i]=min(a[i],MIN[i+1]);int cnt=0;for(int i=2;i<n;i++)if(a[i]>=MAX[i]&&a[i]<=MIN[i])cnt++;printf("%d\n",cnt);}return 0; } View Code

H隊友暴力了下就ok了

#include<bits/stdc++.h> using namespace std;vector< pair<int,int> >cl; char G[55][55]; int main() {int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s",G[i]);int yi=0;for(int i=1;i<n-1;i++)for(int j=1;j<m-1;j++)if(G[i][j]=='1')yi++;cl.clear();for(int i=0;i<=m-2;i++)cl.push_back(make_pair(0,i));for(int i=1;i<=m-1;i++)cl.push_back(make_pair(n-1,i));for(int i=1;i<=n-1;i++)cl.push_back(make_pair(i,0));for(int i=0;i<=n-2;i++)cl.push_back(make_pair(i,m-1));int cnt=0;for(auto x:cl)if(G[x.first][x.second]=='0')cnt++;if(cnt<=yi)printf("%d\n",cnt);else printf("-1\n");}return 0; } View Code

I dp隊友一次過

#include <bits/stdc++.h> using namespace std; int a[200005],jump[200005]; int dp[200005]; int main() {int T,n;scanf("%d",&T);while(T--){map<int,int> ma;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){jump[i]=-1;if(ma[a[i]]) jump[i]=ma[a[i]];ma[a[i]]=i;}dp[0]=-1;for(int i=1;i<=n;i++){dp[i]=dp[i-1]+1;if(jump[i]!=-1) dp[i]=min(dp[i],dp[jump[i]]+1);}printf("%d\n",dp[n]);}return 0; } View Code

J就是個dp的思想，選擇這個數，不選擇，構成一個新的集合

#include <bits/stdc++.h> using namespace std; const int MD=1e9+7; int main() {ios::sync_with_stdio(0);int T;cin>>T;while(T--){int n;cin>>n;long long t=0;for(int i=0,x; i<n; i++)cin>>x,t=(t+t*x+x)%MD;cout<<t<<"\n";}return 0; } View Code

K求這個序列全排列的回文串個數，其實就是和其個數有關，只能有1個奇數，然后就是組合數，重復的除一下就好

#include <bits/stdc++.h> using namespace std; char s[25]; int a[30],fac[15]; int main() {int T,n;scanf("%d",&T);fac[0]=1;for(int i=1;i<=10;i++) fac[i]=fac[i-1]*i;while(T--){memset(a,0,sizeof a);scanf("%d%s",&n,s);for(int i=0;i<n;i++)a[s[i]-'a']++;int f=0;for(int i=0;i<26;i++)f+=(a[i]&1),a[i]>>=1;if(f>1) printf("0\n");else{n/=2;int ans=fac[n];for(int i=0;i<26;i++)ans/=fac[a[i]];printf("%d\n",ans);}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/BobHuang/p/9759662.html

總結

以上是生活随笔為你收集整理的gym101532 2017 JUST Programming Contest 4.0的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。