CCPC2019-湖南全国邀请赛（湘潭大学）
Problem A?Chessboard
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6532
題意：有n個點，其價值為i；分別對某一行、某一列以下的行、列有限制，求選擇棋子的價值和最大
題解：費用流
?????? 離散化坐標，每行用一個點表示，每列也用一個點表示。表示第i-1行的點向表示第i行的點連邊，容量為第i行及以后能拿的棋子數的上限，費用為0，同理表示相鄰列的點兩兩連邊。若第i行第j列上有棋子，則表示第i行的點向表示第j列的點連邊，容量為1，費用為該棋子的價值。可以定義源點表示第0行，匯點表示第0列，源點到匯點的最大費用流即為答案。
C++版本一
題解：最小費用最大流
Dinic+SPFA+二分+離散化
1、離散化坐標，每行用一個點表示，每列也用一個點表示。
2、從0行(0列)遞推到每一行(每一列)可以拿到的棋子，表示第i-1行的點向表示第i行的點連邊，容量為第i行及以后能拿的棋子數的上限，費用為0，同理表示相鄰列的點兩兩連邊。
3、若第i行第j列上有棋子，則表示第i行的點向表示第j列的點連邊，容量為1，費用為該棋子的價值。
4、可以定義源點表示第0行，匯點表示第0列，源點到匯點的最大費用流即為答案。
5、即假設有n行m列，拆分每個點，分為橫坐標和縱坐標，從0行到n行，再從m列到0列。
6、
/* *@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=1000+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 s,t,n,m,p,l,r,u,v; ll k; ll ans,cntX,cntY,flag,temp,sum,minz,maxflow; ll dis[N]; bool vis[N]; int X[N],Y[N],x[N],y[N]; ll wc[N],wr[N]; char str[5]; struct Node{int x,y;ll w;Node(){};Node(int X,int Y,ll W):x(X),y(Y),w(W){} }e[N]; struct node{int u,v;ll c,w;node(){};node(int form,int to,ll cap,ll w):u(form),v(to),c(cap),w(w){} }; vector<node>edge; vector<int> G[N]; void Addedge(int u,int v,ll cap,ll w){edge.push_back({u,v,cap,w});edge.push_back({v,u,0,-w});//cout<<u<<" "<<v<<" "<<cap<<endl;int sz=edge.size();G[u].push_back(sz-2);G[v].push_back(sz-1); } bool bfs(int u){//memset(dis,-1,sizeof(dis));for(int i=0;i<=t;i++)dis[i]=INF,vis[i]=0;dis[u]=0;queue<int>q;q.push(u);vis[u]=1;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=0;i<G[u].size();i++){node e=edge[G[u][i]];//cout<<u<<" "<<e.v<<endl;if(dis[e.v]>dis[u]+e.w&&e.c>0){dis[e.v]=dis[u]+e.w;if(!vis[e.v]){vis[e.v]=1;q.push(e.v);}}}}return dis[t]!=INF; } int dfs(int u,ll flow){vis[u]=1;if(u==t)return flow;int now;for(int i=0;i<G[u].size();i++){node e=edge[G[u][i]];//if((!vis[e.v]||e.v==t)&&e.c>0&&dis[u]+e.w==dis[e.v]&&(now=dfs(e.v,min(flow,e.c)))){ans+=e.w*now;//cout<<now<<endl;edge[G[u][i]].c-=now;edge[G[u][i]^1].c+=now;return now;}}return 0; } void dinic(){while(bfs(s)){//cout<<ans<<endl;int res=0;//memset(vis,0,sizeof(vis));while((res=dfs(s,INF))){maxflow+=res;memset(vis,0,sizeof(vis));}} } void init(){for(int i=0;i<=t;i++)G[i].clear();edge.clear();ans=0;maxflow=0; } 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",&x[i],&y[i]);e[i]=Node(x[i],y[i],i);}sort(x+1,x+n+1);sort(y+1,y+n+1);cntX=cntY=0;X[++cntX]=x[1];Y[++cntY]=y[1];for(int i=2;i<=n;i++)if(x[i-1]!=x[i])X[++cntX]=x[i];for(int i=2;i<=n;i++)if(y[i-1]!=y[i])Y[++cntY]=y[i];s=0;t=cntX+cntY+1;//cout<<s<<" "<<t<<endl;init();scanf("%d",&m);memset(wc,0x3f,sizeof(wc));memset(wr,0x3f,sizeof(wr));for(int i=1;i<=m;i++){scanf("%s%d%lld",str,&p,&k);if(str[0]=='R'){int row=lower_bound(X+1,X+cntX+1,p)-X;//if(X[row]!=p)row--;wr[row]=min(k,wr[row]);}else{int col=lower_bound(Y+1,Y+cntY+1,p)-Y;//if(Y[col]!=p)col--;wc[col]=min(k,wc[col]);}}for(int i=1;i<=cntX;i++){wr[i]=min(wr[i],wr[i-1]);Addedge(i-1,i,wr[i],0);}for(int i=1;i<=cntY;i++){wc[i]=min(wc[i],wc[i-1]);Addedge(t-i,t-i+1,wc[i],0);}for(int i=1;i<=n;i++){int u=lower_bound(X+1,X+cntX+1,e[i].x)-X;int v=lower_bound(Y+1,Y+cntY+1,e[i].y)-Y;Addedge(u,t-v,1,e[i].w);}dinic();cout<<ans<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem B?Build Tree
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6533
題意：一顆m層的滿n叉樹，從k數組中不重復的選擇一些數作為樹的邊，使得所有節點到根節點的距離之和最小
題解：對于一顆m層的滿n叉樹而言，某條邊重復計算的次數是該邊連接的子樹的結點的數量，因為是滿n叉樹，所以這個結點數量是可以O(1)求出的，求min時，只要貪心選擇小的權值為邊賦值，O(E)復雜度內即可算出。而排序復雜度是O(NlogN),所以總復雜度是O(NlogN+E)。
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; ll t,n,m,k,p,l,r,u,v; ll ans,cnt,flag,temp,sum; ll a[N]; char str; struct node{}; 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; } 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("%lld%lld%lld%lld",&k,&m,&n,&p)){for(int i=1;i<=k;i++)scanf("%lld",&a[i]);if(m==0||n==0){cout<<0<<endl;continue;}sort(a+1,a+k+1);int pos=n;int fac=m-1;ans=0;for(int i=1;i<=k;i++){if(!fac)break;ans=(ans+((a[i]%p)*(n==1?fac:(POW(n,fac,p)-1)/(n-1)))%p)%p;//cout<<(ll)(POW(n,fac,p)-1)/(n-1)<<endl;if(i==pos){//cout<<pos<<endl;fac--;pos=pos+POW(n,m-fac,p);}} cout<<ans<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem C?Chika and Friendly Pairs
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6534
題意：給你一個序列，多次詢問，每次讓你回答一個區間中差的絕對值不超過一個給定常數K的元素對數。
題解：對序列中的所有元素以及這些元素+K，-K后的值進行離散化。 然后使用莫隊算法，在莫隊算法的端點移動過程中，新加入一個元素x的過程中，將其插入樹狀數組，查詢[x-K,x+K]范圍的元素數即可。刪除一個元素的過程與其類似。
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[N],r[N],u,v; int ans[N],cnt,flag,temp,tot; int a[N],b[N],c[N],be[N]; char str; struct node{int l,r,id;bool operator <(const node &S)const{return (be[l] ^ be[S.l]) ? be[l] < be[S.l] : ((be[l] & 1) ? r < S.r : r > S.r);} }e[N]; int tree[N]; void add(int x,int C){for(int i=x;i<=tot;i+=i&-i){tree[i]+=C;} } int sum(int x){int res=0;for(int i=x;i>0;i-=i&-i){res+=tree[i];}return res; } 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,&k);int sz = sqrt(n);int bnum = ceil((double)n / sz);for (int i = 1; i <= bnum; i++){for (int j = (i - 1) * sz + 1; j <= i * sz; j++)be[j] = i;}for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+n+1);c[1]=b[1];tot=1;for(int i=2;i<=n;i++)if(b[i-1]!=b[i])c[++tot]=b[i];for(int i=1;i<=m;i++){scanf("%d%d",&e[i].l,&e[i].r);e[i].id=i;}sort(e+1,e+m+1);for (int i = 1; i <= n; i++){l[i] = lower_bound(c+1,c+tot+1, a[i] - k) - c ;r[i] = upper_bound(c+1,c+tot+1, a[i] + k) - c - 1;a[i] = lower_bound(c+1,c+tot+1, a[i]) - c ;}int L = 1, R = 0, temp = 0;for (int i = 1; i <= m; i++){int ql = e[i].l, qr = e[i].r;while(L < ql){add(a[L], -1);temp -= sum(r[L]) - sum(l[L] - 1);L++;}while(L > ql){L--;temp += sum(r[L]) - sum(l[L] - 1);add(a[L], 1);}while(R < qr){R++;temp += sum(r[R]) - sum(l[R] - 1);add(a[R], 1);}while(R > qr){add(a[R], -1);temp -= sum(r[R]) - sum(l[R] - 1);R--;}ans[e[i].id] = temp;//cout<<L<<" "<<R<<endl;//cout<<temp<<endl;}for(int i=1;i<=m;i++){cout<<ans[i]<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }/**//* 5 5 3 2 5 7 1 3 6 6 1 3 2 4 1 5 2 3 */Problem D?Chika and Solid Geometry
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6535
題意：求底面均在z=0平面上，頂點的z坐標大于零的斜圓錐和棱錐的體積并。
題解：
將每個z軸方向的橫截面看做多邊形和圓的面積并，然后對z軸做辛普森積分即可。
多邊形和圓的面積并：面積和-面積交。
多邊形和圓的面積交：將圓心移動到原點，以原點為基準對多邊形進行三角剖分，轉化成計算圓心在原點的圓和有一個頂點在原點的三角形的面積交問題。這個進行大力分類討論即可，細節比較多。
C++版本一
?
Problem E?Hello XTCPC
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6536
題意：不重復元素，求子串為xtCpc的數量最大
題解：這是一道很簡單的貪心題目，因為xtCpc這5個字母各不相同，所以直接采取貪心的策略，對于所有的“x”,“t”,“C”,”p”,”c”按照字母不同分別建立一個隊列，每次貪心的從隊列中找到最前面的沒有使用過的字母，直到有一個隊列為空。
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;string 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--){while(~scanf("%d",&n)){ans=0;cin>>str;queue<int>q[5];for(int i=0;i<n;i++){if(str[i]=='x'){q[0].push(i);}else if(str[i]=='t'){q[1].push(i);}else if(str[i]=='C'){q[2].push(i);}else if(str[i]=='p'){q[3].push(i);}else if(str[i]=='c'){q[4].push(i);}}while(!q[0].empty()){int pos=q[0].front();q[0].pop();flag=1;for(int i=1;i<5;i++){while(!q[i].empty()&&pos>q[i].front())q[i].pop();if(q[i].empty()){flag=0;break;}pos=q[i].front();q[i].pop();}if(!flag)break;ans++;}cout<<ans<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem F?Neko and function
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6537
題意：
題解：
設g(n,k)為k個>=1的數的乘積為n的方案數
很容易推出容斥f(n,k)= sum (-1)^i * g(n,k-i) * C(k,i)
而g(n,k)=prod C(ai+k-1,k-1) 其中n=prod pi^ai pi是n的第i個質因子
可以發現g(n,k)是積性函數，套min-25篩即可
C++版本一
?
Problem G?Neko and quadrilateral
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6538
題意：
題解：
求面積最大和最小四邊形，通過對角線變換為求面積最大和最小三角形
求出任意兩點組成的向量，然后排序
枚舉向量，基于此進行貪心，維護向量左側的點到向量的距離單調，右側的點到向量的距離單調
然后選擇最遠和最近點更新答案
復雜度n^2logn
C++版本一
?
Problem H?Neko and sequence
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6539
題意：
題解：
考慮如果兩種括號都存在，那么移動一定步數后，都會在()上來回移動，可以預處理出每個位置移動多少步后會進入這個循環，或者永遠不進入循環
在進入循環之前一定都是朝一個方向一直移動
?
那么在進入循環之前，起點為i的位置走j步到達的點就是(i+kj)%n
化簡為(i+kj%n)%n，設d=kj%n,把區間詢問以n-d為間隔分成兩部分處理即可，可以用樹狀數組維護出來
進入循環后的部分也可以按j的奇偶用樹狀數組輕松維護出來
總體復雜度nlogn
C++版本一
?
Problem I?Neko and tree
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6540
題意：
題解：
樹形dp
dp[i][j]表示以i為根的子樹中到i最遠的關鍵點距離為j的方案數
當u向fa [u]更新時，進行更新即可
dp[u][i]?dp[fa[u]][j]?[i+j≤k]→new_dp[fa[u]][max?(i+1,j)]
可以用前綴和分兩段優化
求答案時考慮反過來求，用總方案數減去不合法方案數
不合法方案數在可在更新的時候用類似的方法同時求出
C++版本一
?
Problem J?Neko and triangle
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6541
題意：
題解：
本質上是給你x，y，找到一個區間[l,r]使得
sum_x(l,r)*y-sum_y(l,r)*x最大
?
如果把所有sum_x(l,r)和sum_y(l,r)映射成二維平面上的點集的話，我們可以發現答案一定在點集的凸殼上
如果求出這個凸殼，就可以二分答案了
?
這個凸殼可以用分治+閔可夫斯基和來求
C++版本一
?
Problem K?SSY and JLBD
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6542
題意：判斷是否滿足“shisanyao”或者“jiulianbaodeng”的要求
題解：只要根據題意進行簡單的模擬即可，唯一略有麻煩的地方應該就是麻將牌的讀入了。
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[4][10]; int b[2][14]={{0,0,1,1,2,2,3,3,3,3,3,3,3},{1,9,1,9,1,9,1,2,3,4,5,6,7}}; int c[10]={0,3,1,1,1,1,1,1,1,3}; string str; string word[8]={"","dong","nan","xi","bei","zhong","fa","bai"}; 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<=14;i++){cin>>str;if(isdigit(str[0])){if(str[1]=='s'){a[0][str[0]-'0']++;a[0][0]++;}else if(str[1]=='p'){a[1][str[0]-'0']++;a[1][0]++;}else if(str[1]=='w'){a[2][str[0]-'0']++;a[2][0]++;}}else{for(int j=1;j<=7;j++){if(str==word[j]){a[3][j]++;a[3][0]++;break;}}}}flag = 1;for(int i=0;i<13;i++)if(!a[b[0][i]][b[1][i]]){flag=0;break;}if(flag){cout<<"shisanyao!"<<endl;return 0;}for(int i=0;i<3;i++){if(a[i][0]==14){flag=1;for(int j=1;j<=9;j++){if(a[i][j]<c[j]){flag=0;}}if(flag){cout<<"jiulianbaodeng!"<<endl;return 0;}}}cout<<"I dont know!"<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }Problem L?Can you raed it croretcly?
補題地址：http://acm.hdu.edu.cn/showproblem.php?pid=6543
題意：如果單詞的首字母和最后一個字母是正確的，只是交換其他字母，人類可以自動糾正單詞的拼寫。當兩個字符串相同時輸出“Equal”; 輸出“是”時可以更正，否則輸出“否”。
題解：輸入兩個字符串，如果兩者一樣則輸出Equal，不一樣則判斷字符串首尾字母是否相同，中間字母對應個數是否相同，直接輸出結果。
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=300+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]; string str1,str2; 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(cin>>str1){cin>>str2;memset(a,0,sizeof(a));if(str1==str2){cout<<"Equal"<<endl;}else{flag=1;for(int i=0;i<str1.size();i++)a[str1[i]-97]++;for(int i=0;i<str2.size();i++)a[str2[i]-97]--;for(int i=0;i<26;i++)if(a[i])flag=0;cout<<(flag&&str1[0]==str2[0]&&str1[str1.size()-1]==str2[str2.size()-1]?"Yes":"No")<<endl;}//scanf("%d",&n);}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }?
總結
以上是生活随笔為你收集整理的CCPC2019-湖南全国邀请赛（湘潭大学）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C/C++控制台应用程序——画三角形、圆
- 下一篇： Going Home