Problem A?Find the Nth Character

https://ac.nowcoder.com/acm/contest/877/A

題意：定義一個字符串，求第n個字符是什么

題解：

打表

C++版本一

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; char str[N]; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);for(int i=1;i<=200;i++){for(int j=1;j<=i;j++){str[++cnt]='a'+(j%26==0?26:j%26)-1;}}scanf("%d",&t);while(t--){scanf("%d",&n);cout<<str[n]<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem B?Help Me

https://ac.nowcoder.com/acm/contest/877/B

題意：

題解：

完全平方公式，拆分，歸類。

對于ai的平方各有n-1個

對于-2aiaj各1個，用前綴和可以減少復雜度

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; ll ans,cnt,flag,temp,sum; ll a[N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){scanf("%d",&n);ans=0;sum=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);ans-=2*sum*a[i];sum+=a[i];ans+=(n-1)*a[i]*a[i];}cout<<ans<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

Problem C?Challenge IQ

https://ac.nowcoder.com/acm/contest/877/C

題意：在n的所有全排列數組中相鄰互質對數最多有幾對

題解：互質環

肯定存在一個n對的序列

就是1 2 3 4 5 6 7 。。。。。。n

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n",n);}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

?

Problem D?Schedules

https://ac.nowcoder.com/acm/contest/877/D

題意：有n個任務，有固定的開始和結束時間，同一個機器不能同時進行兩個任務，求至少需要幾臺機器

題解：

差分

原題

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,u,v; int ans,cnt,flag,temp,sum; int l[N],r[N]; char str; struct node{int l,r;bool operator <(const node &S)const{if(l==S.l)return r<S.r;return l<S.l;} }e[N]; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){while(~scanf("%d",&n)){for(int i=1;i<=n;i++){//scanf("%d%d",&e[i].l,&e[i].r);scanf("%d%d",&l[i],&r[i]);}//sort(e+1,e+n+1);sort(l+1,l+n+1);sort(r+1,r+n+1);int x=1;int y=1;ans=0;t=0;for(int i=0;i<=N;i++){//while(e[x].l==i&&x<=n)x++,t++;//while(e[y].r==i&&y<=n)y++,t--;while(l[x]==i&&x<=n)x++,t++;while(r[y]==i&&y<=n)y++,t--;ans=max(ans,t);}cout<<ans<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem E?Pig-Palindromic

https://ac.nowcoder.com/acm/contest/877/E

題意：求一個長度為偶數，而且對稱位置分別為大寫小寫字母或者小寫大寫字母的子字符串的長度

C++版本一

題解：

最長回文子串

改下條件==變成絕對值為32

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a[N]; char str[N]; struct node{};int longestPalindrome(string s) {//尋找最長回文子串int sz = s.size();if (sz <= 1) return 0;//用動態規劃方法//dp為size*size大小的矩陣，dp[i][j]表示以s[i]開頭，s[j]結尾的回文串長度（如果不是回文串，則為0）vector<vector<int>> dp(sz);for (int i = 0; i<sz; i++) {for (int j = 0; j<sz; j++) {//初始化，將對角線元素設為1if(i==j) dp[i].push_back(1);else dp[i].push_back(0);}}int start = 0, maxl = 0;for (int j = 0; j < sz;j++){for (int i = j - 1; i >= 0; i--) {if (abs(s[i]-s[j])==32) {if(j-i==1) dp[i][j] = 2;else {if (dp[i + 1][j - 1]>0) {dp[i][j] = dp[i + 1][j - 1] + 2;}else dp[i][j] = 0;}}else dp[i][j] = 0;if (dp[i][j]%2==0&&dp[i][j]>maxl) {maxl = dp[i][j]; start = i;}}}return maxl; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){//scanf("%d",&n);cin>>str;cout<<longestPalindrome(str)<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

題解：枚舉相鄰兩點，向兩邊推；

#include<iostream> #include<algorithm> using namespace std; int main() {string a;while(cin>>a){int cnt;int maxn=-9999999;for(int i=0;i<a.size();i++){cnt=0;for(int k=i,w=i+1;k>=0&&w<a.size();){if(a[k]+32==a[w]||a[k]-32==a[w]){cnt+=2;k--;w++;}elsebreak;} maxn=max(maxn,cnt);}cout<<maxn<<endl;} }

Problem F?GCD Problem

https://ac.nowcoder.com/acm/contest/877/F

題解：一個數組，有0 1兩種操作，0操作代表區間[l，r]中的所有元素變成，1操作代表求[l，r]的最大公約數

題解：線段樹+結論

對于0操作每一個數最多操作8次，所以可以用線段樹更新，只要標記一下，這個點已經不能更新了

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=200000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; char str; struct node{}; ll tree[N<<2]; bool tag[N<<2]; void pushup(int rt){tree[rt]=__gcd(tree[rt<<1],tree[rt<<1|1]);tag[rt]=tag[rt<<1]&&tag[rt<<1|1]; } void build(int l,int r,int rt){if(l==r){scanf("%lld",&tree[rt]);tag[rt]=0;return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);} void updata(int l,int r,int rt,int L,int R){if(tag[rt])return;if(l==r){tree[rt]=sqrt(tree[rt]);if(tree[rt]==1)tag[rt]=1;return;}int mid=(l+r)>>1;if(L<=mid)updata(l,mid,rt<<1,L,R);if(R>mid)updata(mid+1,r,rt<<1|1,L,R);pushup(rt); } ll query(int l,int r,int rt,int L,int R){if(tag[rt]&&l<=L&&R<=r){return 1;}if(L<=l&&r<=R){return tree[rt];}int mid=(l+r)>>1;if(R<=mid)return query(l,mid,rt<<1,L,R);else if(L>mid)return query(mid+1,r,rt<<1|1,L,R);else return __gcd(query(l,mid,rt<<1,L,R),query(mid+1,r,rt<<1|1,L,R)); } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d",&n);memset(tree,0,sizeof(tree));build(1,n,1);scanf("%d",&m);while(m--){scanf("%d%d%d",&t,&l,&r);if(t==0){updata(1,n,1,l,r);}else{cout<<query(1,n,1,l,r)<<endl;}}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

?

Problem G?Bash Game

https://ac.nowcoder.com/acm/contest/877/G

題意：有一拍賣品成交價為P，兩人輪流出價，至少加價1，最多加價M，兩個人都足夠聰明，求最后誰會拍下

題解：巴什博奕

當且僅當(n-1)%(m+1)==0時Bob能贏

參考文章：巴什博奕

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a[N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);cout<<((n-1)%(m+1)==0?"Bob":"Alice")<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem H?Pass CET 6

https://ac.nowcoder.com/acm/contest/877/H

題意：每天只能背一行或者一列的單詞，求一個代表單詞的矩陣，其值為這個單詞最后背是第幾天

C++版本一

題解：

貪心

只標記行列最后一次，比較最后的行列最大值

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum;char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d%d%d",&n,&m,&t);int a[n+10][m+10];for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)a[i][j]=0;for(int i=1;i<=t;i++){scanf("%d%d",&k,&p);if(k==1){a[p][0]=i;}else{a[0][p]=i;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=max(a[0][j],a[i][0]);}for(int j=1;j<=m;j++){printf("%d%c",a[i][j]," \n"[j==m]);}}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

Problem I?Center Street

https://ac.nowcoder.com/acm/contest/877/I

題意：n個倉庫，如果兩個倉買A,B滿足A是B的倍數，則A,B之間可以通一條路,當然這些路是雙向的，A可以到B，B可以到A，如果倉買A,B之間通路，則過路費，從1號出發，求到每個倉庫的最小花費，

題解：篩法

參考文章：線性篩

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=500000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; ll dis[N]; int prime[N],tag[N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){memset(tag,0,sizeof(tag));int cnt=0;tag[0]=tag[1]=1;for(int i = 2; i<N; i++){if(!tag[i]){prime[cnt++]=i;dis[i]=(ll)(i-1)*(i-1);}for(int j=0;j<cnt && prime[j]*i<N; j++){tag[i*prime[j]] = 1;dis[i*prime[j]] = dis[i] + (ll)i*i*(prime[j]-1)*(prime[j]-1);if(i % prime[j]==0){break;}}}scanf("%d",&n);for(int i=1;i<=n;i++){printf("%lld%c",dis[i]," \n"[i==n]);}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

Problem J?Special Distance

https://ac.nowcoder.com/acm/contest/877/J

題意：求最大FST距離

題解：

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=300000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; ll ans,cnt,flag,temp,sum; ll a[N],b[N]; char str; struct node{ ll x,y; }; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){scanf("%d",&n);ans=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);a[i]*=a[i];b[i]=(ll)i*i;}node mx,mn;mx.x=1;mx.y=a[1];mn=mx;for(int i=2;i<=n;i++){ans=max(ans,a[i]-mn.y+b[i]-mn.x);ans=max(ans,mx.y-a[i]+b[i]-mx.x);if(a[i]-b[i]>mx.y-mx.x){mx.x=b[i];mx.y=a[i];}if(-a[i]-b[i]>-mn.y-mn.x){mn.x=b[i];mn.y=a[i];}}cout<<ans<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

Problem K?Maximum Sum of Digits

https://ac.nowcoder.com/acm/contest/877/K

題意：將n分成兩個數，使得兩個數每一位的數字加起來最大

題解：

CF原題

貪心

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; ll t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a[N]; char str; struct node{}; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){scanf("%lld",&n);if(n==0){cout<<0<<endl;continue;}m=n;ans=0;sum=0;while(n){sum++;n/=10;}ans=(sum-1)*9;m-=pow(10,sum-1)-1;while(m){ans+=m%10;m/=10;}cout<<ans<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的2019黑龙江大学程序设计竞赛的全部內容，希望文章能夠幫你解決所遇到的問題。

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