“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学)
生活随笔
收集整理的這篇文章主要介紹了
“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Problem A?小花梨的字符串
https://acm.ecnu.edu.cn/contest/173/problem/A/
題意：對區間子字符串排列，使得滿足條件，求排列最長。
題解：
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; int a[N]; 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);//scanf("%d",&t);//while(t--){scanf("%d%d",&n,&m);cin>>str;for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);cout<<(r-l+1)*(r-l+2)/2<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem B?小花梨的三角形
https://acm.ecnu.edu.cn/contest/173/problem/B/
題意：統計三個頂點不完全相同的三角形個數。
題解：枚舉
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=100+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; bool vis[N][N][N]; char str[N][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);//scanf("%d",&t);//while(t--){scanf("%d",&n);for(int i=1;i<=n+1;i++)scanf("%s",str[i]+1);for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){for(int k=i+1;k<=n+1;k++){int a[4];a[0]=str[k][j]-'a';a[1]=str[i][j]-'a';a[2]=str[k][j+k-i]-'a';sort(a,a+3);//cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;vis[a[0]][a[1]][a[2]]=1;}}}for(int i=2;i<=n;i++){for(int j=1;j<i;j++){for(int k=j+1;k<=i&&i+k-j<=n+1;k++){int a[4];a[0]=str[i][j]-'a';a[1]=str[i][k]-'a';a[2]=str[i+k-j][k]-'a';sort(a,a+3);//cout<<i<<" "<<j<<" "<<k<<" "<<i+k-j<<endl;//cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;vis[a[0]][a[1]][a[2]]=1;}}}for(int i=0;i<26;i++){for(int j=i;j<26;j++){for(int k=j;k<26;k++){ans+=vis[i][j][k];}}}cout<<ans<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem C?小花梨判連通
https://acm.ecnu.edu.cn/contest/173/problem/C/
題意：有K張聯通圖，求使得 ?和?在這 ?張圖中都是連通的j的個數
C++版本一
題解：直接 dfs 、BFS 或者并查集對每張圖進行連通塊染色， 或者并查集對每張圖進行連通塊染色，? 兩個點在 k張圖中都相鄰說明這兩個點在 張圖中都相鄰說明這兩個點在 張圖中都相鄰說明這兩個點在 k張圖的染色 都是一樣的?
map<vector<int>,int>存下每個點在 k張圖的顏色序? 列出現的次數即可?
C++版本二
?題解：對每一個圖dfs求聯通塊并染色，處于同一個聯通塊中的點染成相同的顏色。染色之后對于圖中的每一個點就有一個長度為k的顏色序列，兩點在k張圖中均聯通即兩個點的顏色序列完全相同。求每個點的顏色序列的hash值，并記錄每種hash值出現了多少次。輸出答案時將該點對應的hash值出現的次數輸出即可。
#include "bits/stdc++.h"using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int maxn = 1e5 + 100; const int inf = 0x3f3f3f3f; bool vis[maxn]; vector<int> e[11][maxn]; unsigned long long ans[maxn]; int c[11][maxn]; int col = 0; map<unsigned long long, int> mp;void dfs(int deep, int now) {if (vis[now]) return;c[deep][now] = col;vis[now] = true;for (auto p:e[deep][now]) {dfs(deep, p);} }int main() {//freopen("in.txt", "r", stdin);int n, k, m;scanf("%d %d", &n, &k);int u, v;for (int i = 0; i < k; i++) {cin >> m;for (int j = 0; j < m; j++) {scanf("%d %d", &u, &v);e[i][u].push_back(v);e[i][v].push_back(u);}col = 0;memset(vis, 0, sizeof(vis));for (int j = 1; j <= n; j++) {if (!vis[j]) col++;dfs(i, j);}}unsigned long long hash;for (int i = 1; i <= n; i++) {hash = 0;for (int j = 0; j < k; j++) {hash = hash * mod + c[j][i];}mp[hash]++;ans[i] = hash;}for (int i = 1; i <= n; i++) {cout << mp[ans[i]] << endl;}return 0; }Problem D?小花梨的取石子游戲
https://acm.ecnu.edu.cn/contest/173/problem/D/
題意：按規則取石子，求第i輪必勝的人
題解：博弈，誰先拿到非1的堆，誰就是贏家。因為足夠聰明，所有人必然使得自己永遠占先機。
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=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; int a[N],b[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);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i+n]=a[i];}flag=2*n+1;for(int i=2*n;i>=1;i--){if(a[i]!=1)flag=i;b[i]=flag;}for(int i=1;i<=n;i++){cout<<((min(n-1,b[i]-i))%2==0?"First":"Second")<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem E?小花梨的數組
https://acm.ecnu.edu.cn/contest/173/problem/E/
題意：
題解：線段樹+tag標記
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=1000000+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 f[M],prime[M],pre[N]; ll tree[N<<2],tag[N<<2]; ll POW(ll a,ll b,ll c){ll res=1;ll base=a%c;while(b){if(b&1)res=(res*base)%c;base=(base*base)%c;b>>=1;}return res; }void init(){f[1]=1;prime[0]=prime[1]=1;for(int i=2;i<=1e6;i++){if(prime[i]==0){pre[++cnt]=i;f[i]=i;}for(int j=1;j<=cnt&&pre[j]*i<=1e6;j++){prime[i*pre[j]]=1;f[i*pre[j]]=pre[j];if(i%pre[j]==0){break;}}} } void pushup(int rt){tree[rt]=tree[rt<<1]+tree[rt<<1|1]; } void pushdowm(int rt){tag[rt<<1]+=tag[rt];tag[rt<<1|1]+=tag[rt];tag[rt]=0; } 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 updata1(int l,int r,int rt,int L,int R){if(tree[rt]==r-l+1)return;if(L<=l&&r<=R){tag[rt]++;return;}pushdowm(rt);int mid=(l+r)>>1;if(L<=mid)updata1(l,mid,rt<<1,L,R);if(R>mid)updata1(mid+1,r,rt<<1|1,L,R);pushup(rt); } void updata2(int l,int r,int rt,int L,int R){if(tree[rt]==r-l+1)return;if(L<=l&&r<=R&&tag[rt]){tag[rt]--;return;}if(l==r){tree[rt]=tree[rt]/f[tree[rt]]%MOD;return;}pushdowm(rt);int mid=(l+r)>>1;if(L<=mid)updata2(l,mid,rt<<1,L,R);if(R>mid)updata2(mid+1,r,rt<<1|1,L,R);pushup(rt); } ll query(int l,int r,int rt,int L){if(tree[rt]==r-l+1)return 1;if(l==r){return tree[rt]*POW(f[tree[rt]],tag[rt],MOD)%MOD;}pushdowm(rt);int mid=(l+r)>>1;if(L<=mid)return query(l,mid,rt<<1,L);else return query(mid+1,r,rt<<1|1,L); } 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);init();while(~scanf("%d%d",&n,&m)){memset(tree,0,sizeof(tree));build(1,n,1);for(int i=1;i<=m;i++){scanf("%d",&k);if(k==1){scanf("%d%d",&l,&r);updata1(1,n,1,l,r);}else if(k==2){scanf("%d%d",&l,&r);updata2(1,n,1,l,r);}else{scanf("%d",&l);cout<<query(1,n,1,l)<<endl;}}}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem F?小花梨的無向圖
https://acm.ecnu.edu.cn/contest/173/problem/F/
題意：
題解：
C++版本一
?
Problem G?小花梨的函數
https://acm.ecnu.edu.cn/contest/173/problem/G/
題意：
題解：
C++版本一
?
Problem H?小花梨的矩陣
https://acm.ecnu.edu.cn/contest/173/problem/H/
題意：
題解：
C++版本一
?
Problem I?小花梨點外賣
https://acm.ecnu.edu.cn/contest/173/problem/I/
題意：有兩種優惠，最多選擇一種，使得付款最小
題解：模擬
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,a,b,c,d; ll ans,cnt,flag,temp,sum; int v[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%d%d%d",&n,&a,&b,&c,&d);for(int i=1;i<=n;i++){scanf("%d",&v[i]);sum+=v[i];}if(sum>=a&&sum>=c){ans=sum-max(b,d);}else if(sum>=a){ans=sum-b;}else if(sum>=c){ans=sum-d;}else{ans=sum;}cout<<ans<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }?
總結
以上是生活随笔為你收集整理的“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 牛客练习赛46
- 下一篇： C/C++控制台应用程序——画三角形、圆