---

layout: post
title: (寒假開黑gym)2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces

---

傳送門

付隊！

許老師！

B.Buildings （polya定理）

題意

B：給你m面墻，每面墻是n*n的格子，你有c種顏色，問你有多少種涂色方案。用polya定理

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=3e5+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; ///a<mod 并且 p為素數 ll pow_mod(ll x, ll n, ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res; } ll inv(ll a,ll p){return pow_mod(a,p-2,p);} int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int n,m,c;cin>>n>>m>>c;ll ans=0;for(int i=0;i<m;i++){ans+=pow_mod(c,n*n*__gcd(i,m),mod);ans%=mod;}cout<<ans*inv(m,mod)%mod<<endl;return 0; }

C.Joyride （分層圖最短路）

題意

C：游樂場有n個設施，有m條人行道，游樂設施會花費ti的時間和pi的錢，人行道需要花費t的時間，你需要用最少的錢恰好游玩x的時間，起點是1，終點是1，求最少的錢是多少4

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1e3+50; const int inf=1e9+7; int x,n,m,t; vector<int>ve[maxn]; struct need{int t,p; }ned[maxn]; struct node{int in;int w;int time; }; int dis[maxn][maxn]; void dij(){queue<node>q;q.push(node{1,ned[1].p,ned[1].t});for(int i=0;i<=1000;i++){for(int j=0;j<=1000;j++)dis[i][j]=inf;}dis[1][ned[1].t]=ned[1].p;while(!q.empty()){node now=q.front();q.pop();int in=now.in,w=now.w,time=now.time;if(time+ned[in].t<=x&&w+ned[in].p<dis[in][time+ned[in].t]){dis[in][time+ned[in].t]=w+ned[in].p;q.push(node{in,dis[in][time+ned[in].t],time+ned[in].t});}for(int i=0;i<ve[in].size();i++){int nex=ve[in][i];int nextime=time+t+ned[nex].t;if(nextime<=x&&dis[nex][nextime]>w+ned[nex].p){dis[nex][nextime]=w+ned[nex].p;q.push(node{nex,w+ned[nex].p,nextime});}}} }int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);cin>>x>>n>>m>>t;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;ve[a].push_back(b);ve[b].push_back(a);}for(int i=1;i<=n;i++){cin>>ned[i].t>>ned[i].p;}dij();if(dis[1][x]==inf)cout<<"It is a trap."<<endl;else cout<<dis[1][x]<<endl;return 0; }

D.Pants On Fire (map+dfs,or 傳遞閉包)

題意

D 有n個已知串，給m個串，讓你去判斷他們是對的還是錯的還是未知的

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1e3+50; const int inf=1e9+7; map<string,int>mp; int cnt; bool ok[500][500]; int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);string a,b,c,d,e;int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a>>b>>c>>d>>e;if(!mp[a])mp[a]=++cnt;if(!mp[e])mp[e]=++cnt;ok[mp[a]][mp[e]]=true;}for(int k=1;k<=cnt;k++){for(int i=1;i<=cnt;i++){for(int j=1;j<=cnt;j++){ok[i][j]|=ok[i][k]&&ok[k][j];}}}for(int i=1;i<=m;i++){cin>>a>>b>>c>>d>>e;if(!mp[a]||!mp[e]){cout<<"Pants on Fire"<<endl;continue;}int u=mp[a],v=mp[e];if(ok[u][v])cout<<"Fact"<<endl;else if(ok[v][u])cout<<"Alternative Fact"<<endl;else{cout<<"Pants on Fire"<<endl;}}return 0; } #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1e3+50; const int inf=1e9+7; map<string,int>mp; int cnt; vector<int>G[maxn]; bool dfs(int u,int v){for(int i=0;i<G[u].size();i++){if(G[u][i]==v)return true;bool ok=dfs(G[u][i],v);if(ok)return true;}return false; } int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);string a,b,c,d,e;int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a>>b>>c>>d>>e;if(!mp[a])mp[a]=++cnt;if(!mp[e])mp[e]=++cnt;G[mp[a]].push_back(mp[e]);}for(int i=1;i<=m;i++){cin>>a>>b>>c>>d>>e;if(!mp[a]||!mp[e]){cout<<"Pants on Fire"<<endl;continue;}int u=mp[a],v=mp[e];if(dfs(u,v))cout<<"Fact"<<endl;else if(dfs(v,u))cout<<"Alternative Fact"<<endl;else{cout<<"Pants on Fire"<<endl;}}return 0; }

F.Plug It In (匈牙利算法/二分圖匹配/網絡流)

題意

m個插口，n個電器 k個可以匹配的連接 ,問你最大匹配數，但是你有一次機會把一個接口變成三個一樣的

思路

考慮暴力每次暴力把一個其中一個接口數+2跑匈牙利算法，復雜度N^3，然后發現其實第一次跑的最初的圖是可以一直重復利用的，然后就直接把后面的多出來的接口拿去跑增廣路就行。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=3e5+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; /// 二分圖最大基數匹配int mp[1550][1550]; int link[1550]; int n,m,k; bool vis[1550]; int remain[1550]; bool match(int u){for(int i=1;i<=m;i++){if(vis[i]==0&&mp[u][i]){vis[i]=1;if(link[i]==-1||match(link[i])){link[i]=u;return 1;}}}return 0; }int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int k;cin>>n>>m>>k;memset(link,-1,sizeof(link));for(int i=1;i<=k;i++){int a,b;cin>>a>>b;mp[a][b]=1;}int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(match(i))ans++;}for(int i=1;i<=m;i++){remain[i]=link[i];}int mx=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)mp[n+1][j]=mp[n+2][j]=mp[i][j];for(int i=1;i<=m;i++){link[i]=remain[i];}int now=0;memset(vis,0,sizeof(vis));for(int j=n+1;j<=n+2;j++){if(match(j))now++;}mx=max(now,mx);}cout<<ans+mx<<endl;return 0; }

G.Water Testing (皮克定理)

題意

給你一個多邊形問你多邊形中的整點個數有多少

思路

皮克定理

皮克定理是指一個計算點陣中頂點在格點上的多邊形面積公式，該公式可以表示為2S=2a+b-2，其中a表示多邊形內部的點數，b表示多邊形邊界上的點數，S表示多邊形的面積。

其中，面積用每兩條線的叉積計算

當O點為原點時，根據向量的叉積計算公式，各個三角形的面積計算如下：

S_OAB = 0.5(A_xB_y - A_y*B_x) 【(A_x，A_y)為A點的坐標】

S_OBC = 0.5(B_xC_y - B_y*C_x)

S_OCD = 0.5(C_xD_y - C_y*D_x)

S_ODE = 0.5(D_xE_y - D_y*E_x)

S_OEA = 0.5(E_xA_y - E_y*A_x)

邊界的點數用gcd(a.x-b.x,a.y-b.y)計算

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=3e5+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; struct Point{ll x,y; }my[maxn]; int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int n;cin>>n;for(int i=0;i<n;i++){cin>>my[i].x>>my[i].y;}ll s=0,b=0;for(int i=0;i<n;i++){s+=my[i].x*my[(i+1)%n].y-my[(i+1)%n].x*my[i].y;b+=__gcd(abs(my[i].x-my[(i+1)%n].x),abs(my[i].y-my[(i+1)%n].y));}s/=2;s=abs(s);cout<<s-b/2+1<<endl;return 0; }

I.Uberwatch (基礎DP)

思路

對于每個點考慮兩種情況，如果他不放必殺技那
\[ dp[i]=dp[i-1] \]
如果他放必殺技，那么他就只能在i-m時間之前放的最大值加起來
\[ dp[i]=dp[i-m]+a[i] \]

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=3e5+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; int a[maxn]; int dp[maxn]; int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}int sum=0;for(int i=m+1;i<=n;i++){dp[i]=max(dp[i-1],dp[i-m]+a[i]);}cout<<dp[n]<<endl;return 0; }

K.You Are Fired (簽到)

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1e5+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; struct node{ll money;string name;}my[maxn]; bool vis[maxn]; int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);ll n,d,k;cin>>n>>d>>k;for(int i=1;i<=n;i++){cin>>my[i].name>>my[i].money;}sort(my+1,my+1+n,[](node a,node b){return a.money>b.money;});ll ans=0,num=0;for(int i=1;i<=k;i++){ans+=my[i].money;vis[i]=true;num++;if(ans>=d)break;}if(ans<d)cout<<"impossible"<<endl;else{cout<<num<<endl;for(int i=1;i<=n;i++){if(vis[i])cout<<my[i].name<<", YOU ARE FIRED!"<<endl;}}return 0; }

轉載于:https://www.cnblogs.com/luowentao/p/10376667.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的(寒假开黑gym)2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)的全部內容，希望文章能夠幫你解決所遇到的問題。

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