<a href="https://codeforces.com/gym/101933/" target="\_blank" style="font-size:24px;"><strong>传送门</strong></a>
B.Buildings （polya定理）
题意
B：给你m面墙，每面墙是n*n的格子，你有c种颜色，问你有多少种涂色方案。用polya定理
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4const ll mod=1e9+7; 5const int maxn=3e5+50; 6const ll inf=0x3f3f3f3f3f3f3f3fLL; 7///a<mod 并且 p为素数 8ll pow_mod(ll x, ll n, ll mod){ 9 ll res=1; 10 while(n){ 11 if(n&1)res=res*x%mod; 12 x=x*x%mod; 13 n>>=1; 14 } 15 return res; 16} 17ll inv(ll a,ll p){return pow_mod(a,p-2,p);} 18int main() 19{ 20 std::ios::sync_with_stdio(false); 21 std::cin.tie(0); 22 std::cout.tie(0); 23 int n,m,c; 24 cin>>n>>m>>c; 25 ll ans=0; 26 for(int i=0;i<m;i++){ 27 ans+=pow_mod(c,n*n*__gcd(i,m),mod); 28 ans%=mod; 29 } 30 cout<<ans*inv(m,mod)%mod<<endl; 31 return 0; 32}
C.Joyride （分层图最短路）
题意
C：游乐场有n个设施，有m条人行道，游乐设施会花费ti的时间和pi的钱，人行道需要花费t的时间，你需要用最少的钱恰好游玩x的时间，起点是1，终点是1，求最少的钱是多少4
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4const ll mod=998244353; 5const int maxn=1e3+50; 6const int inf=1e9+7; 7int x,n,m,t; 8vector<int>ve[maxn]; 9struct need{ 10 int t,p; 11}ned[maxn]; 12struct node{ 13 int in; 14 int w; 15 int time; 16}; 17int dis[maxn][maxn]; 18void dij(){ 19 queue<node>q; 20 q.push(node{1,ned[1].p,ned[1].t}); 21 for(int i=0;i<=1000;i++){ 22 for(int j=0;j<=1000;j++)dis[i][j]=inf; 23 } 24 dis[1][ned[1].t]=ned[1].p; 25 while(!q.empty()){ 26 node now=q.front(); 27 q.pop(); 28 int in=now.in,w=now.w,time=now.time; 29 if(time+ned[in].t<=x&&w+ned[in].p<dis[in][time+ned[in].t]){ 30 dis[in][time+ned[in].t]=w+ned[in].p; 31 q.push(node{in,dis[in][time+ned[in].t],time+ned[in].t}); 32 } 33 for(int i=0;i<ve[in].size();i++){ 34 int nex=ve[in][i]; 35 int nextime=time+t+ned[nex].t; 36 if(nextime<=x&&dis[nex][nextime]>w+ned[nex].p){ 37 dis[nex][nextime]=w+ned[nex].p; 38 q.push(node{nex,w+ned[nex].p,nextime}); 39 } 40 } 41 } 42} 43 44int main() 45{ 46 std::ios::sync_with_stdio(false); 47 std::cin.tie(0); 48 std::cout.tie(0); 49 cin>>x>>n>>m>>t; 50 for(int i=1;i<=m;i++){ 51 int a,b; 52 cin>>a>>b; 53 ve[a].push_back(b); 54 ve[b].push_back(a); 55 } 56 for(int i=1;i<=n;i++){ 57 cin>>ned[i].t>>ned[i].p; 58 } 59 dij(); 60 if(dis[1][x]==inf)cout<<"It is a trap."<<endl; 61 else cout<<dis[1][x]<<endl; 62 return 0; 63}
D.Pants On Fire (map+dfs,or 传递闭包)
题意
D 有n个已知串，给m个串，让你去判断他们是对的还是错的还是未知的
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4const ll mod=998244353; 5const int maxn=1e3+50; 6const int inf=1e9+7; 7map<string,int>mp; 8int cnt; 9bool ok[500][500]; 10int main() 11{ 12 std::ios::sync_with_stdio(false); 13 std::cin.tie(0); 14 std::cout.tie(0); 15 string a,b,c,d,e; 16 int n,m; 17 cin>>n>>m; 18 for(int i=1;i<=n;i++){ 19 cin>>a>>b>>c>>d>>e; 20 if(!mp[a])mp[a]=++cnt; 21 if(!mp[e])mp[e]=++cnt; 22 ok[mp[a]][mp[e]]=true; 23 } 24 for(int k=1;k<=cnt;k++){ 25 for(int i=1;i<=cnt;i++){ 26 for(int j=1;j<=cnt;j++){ 27 ok[i][j]|=ok[i][k]&&ok[k][j]; 28 } 29 } 30 } 31 for(int i=1;i<=m;i++){ 32 cin>>a>>b>>c>>d>>e; 33 if(!mp[a]||!mp[e]){cout<<"Pants on Fire"<<endl;continue;} 34 int u=mp[a],v=mp[e]; 35 if(ok[u][v])cout<<"Fact"<<endl; 36 else if(ok[v][u])cout<<"Alternative Fact"<<endl; 37 else{ 38 cout<<"Pants on Fire"<<endl; 39 } 40 } 41 return 0; 42} 43 44 45 46#include<bits/stdc++.h> 47using namespace std; 48typedef long long ll; 49const ll mod=998244353; 50const int maxn=1e3+50; 51const int inf=1e9+7; 52map<string,int>mp; 53int cnt; 54vector<int>G[maxn]; 55bool dfs(int u,int v){ 56 57 for(int i=0;i<G[u].size();i++){ 58 if(G[u][i]==v)return true; 59 bool ok=dfs(G[u][i],v); 60 if(ok)return true; 61 } 62 return false; 63} 64int main() 65{ 66 std::ios::sync_with_stdio(false); 67 std::cin.tie(0); 68 std::cout.tie(0); 69 string a,b,c,d,e; 70 int n,m; 71 cin>>n>>m; 72 for(int i=1;i<=n;i++){ 73 cin>>a>>b>>c>>d>>e; 74 if(!mp[a])mp[a]=++cnt; 75 if(!mp[e])mp[e]=++cnt; 76 G[mp[a]].push_back(mp[e]); 77 } 78 for(int i=1;i<=m;i++){ 79 cin>>a>>b>>c>>d>>e; 80 if(!mp[a]||!mp[e]){cout<<"Pants on Fire"<<endl;continue;} 81 int u=mp[a],v=mp[e]; 82 if(dfs(u,v))cout<<"Fact"<<endl; 83 else if(dfs(v,u))cout<<"Alternative Fact"<<endl; 84 else{ 85 cout<<"Pants on Fire"<<endl; 86 } 87 } 88 return 0; 89}
F.Plug It In (匈牙利算法/二分图匹配/网络流)
题意
m个插口，n个电器 k个可以匹配的连接 ,问你最大匹配数，但是你有一次机会把一个接口变成三个一样的
思路
考虑暴力每次暴力把一个其中一个接口数+2跑匈牙利算法，复杂度N^3，然后发现其实第一次跑的最初的图是可以一直重复利用的，然后就直接把后面的多出来的接口拿去跑增广路就行。
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4const ll mod=1e9+7; 5const int maxn=3e5+50; 6const ll inf=0x3f3f3f3f3f3f3f3fLL; 7/// 二分图最大基数匹配 8 9int mp[1550][1550]; 10int link[1550]; 11int n,m,k; 12bool vis[1550]; 13int remain[1550]; 14bool match(int u){ 15 for(int i=1;i<=m;i++){ 16 if(vis[i]==0&&mp[u][i]){ 17 vis[i]=1; 18 if(link[i]==-1||match(link[i])){ 19 link[i]=u; 20 return 1; 21 } 22 } 23 } 24 return 0; 25} 26 27 28int main() 29{ 30 std::ios::sync_with_stdio(false); 31 std::cin.tie(0); 32 std::cout.tie(0); 33 int k; 34 cin>>n>>m>>k; 35 memset(link,-1,sizeof(link)); 36 for(int i=1;i<=k;i++){ 37 int a,b; 38 cin>>a>>b; 39 mp[a][b]=1; 40 } 41 int ans=0; 42 for(int i=1;i<=n;i++){ 43 memset(vis,0,sizeof(vis)); 44 if(match(i))ans++; 45 } 46 for(int i=1;i<=m;i++){ 47 remain[i]=link[i]; 48 } 49 int mx=0; 50 for(int i=1;i<=n;i++){ 51 for(int j=1;j<=m;j++)mp[n+1][j]=mp[n+2][j]=mp[i][j]; 52 for(int i=1;i<=m;i++){ 53 link[i]=remain[i]; 54 } 55 int now=0; 56 memset(vis,0,sizeof(vis)); 57 for(int j=n+1;j<=n+2;j++){ 58 if(match(j))now++; 59 } 60 mx=max(now,mx); 61 } 62 cout<<ans+mx<<endl; 63 return 0; 64}
G.Water Testing (皮克定理)
题意
给你一个多边形问你多边形中的整点个数有多少
思路
皮克定理
皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。
其中，面积用每两条线的叉积计算
当O点为原点时，根据向量的叉积计算公式，各个三角形的面积计算如下：
S_OAB = 0.5*(A_x_B_y - A_y_B_x) 【(A_x，A_y)为A点的坐标】
S_OBC = 0.5*(B_x_C_y - B_y_C_x)
S_OCD = 0.5*(C_x_D_y - C_y_D_x)
S_ODE = 0.5*(D_x_E_y - D_y_E_x)
S_OEA = 0.5*(E_x_A_y - E_y_A_x)
边界的点数用gcd(a.x-b.x,a.y-b.y)计算
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4const ll mod=998244353; 5const int maxn=3e5+50; 6const ll inf=0x3f3f3f3f3f3f3f3fLL; 7struct Point{ 8 ll x,y; 9}my[maxn]; 10int main() 11{ 12 std::ios::sync_with_stdio(false); 13 std::cin.tie(0); 14 std::cout.tie(0); 15 int n; 16 cin>>n; 17 for(int i=0;i<n;i++){ 18 cin>>my[i].x>>my[i].y; 19 } 20 ll s=0,b=0; 21 for(int i=0;i<n;i++){ 22 s+=my[i].x*my[(i+1)%n].y-my[(i+1)%n].x*my[i].y; 23 b+=__gcd(abs(my[i].x-my[(i+1)%n].x),abs(my[i].y-my[(i+1)%n].y)); 24 } 25 26 s/=2; 27 s=abs(s); 28 cout<<s-b/2+1<<endl; 29 return 0; 30}
I.Uberwatch (基础DP)
思路
对于每个点考虑两种情况，如果他不放必杀技那 $$ dp[i]=dp[i-1] $$ 如果他放必杀技，那么他就只能在i-m时间之前放的最大值加起来 $$ dp[i]=dp[i-m]+a[i] $$
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4const ll mod=998244353; 5const int maxn=3e5+50; 6const ll inf=0x3f3f3f3f3f3f3f3fLL; 7int a[maxn]; 8int dp[maxn]; 9int main() 10{ 11 std::ios::sync_with_stdio(false); 12 std::cin.tie(0); 13 std::cout.tie(0); 14 int n,m; 15 cin>>n>>m; 16 for(int i=1;i<=n;i++){ 17 cin>>a[i]; 18 } 19 int sum=0; 20 for(int i=m+1;i<=n;i++){ 21 dp[i]=max(dp[i-1],dp[i-m]+a[i]); 22 } 23 cout<<dp[n]<<endl; 24 return 0; 25}
K.You Are Fired (签到)
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4const ll mod=998244353; 5const int maxn=1e5+50; 6const ll inf=0x3f3f3f3f3f3f3f3fLL; 7struct node{ 8 ll money; 9 string name; 10 11}my[maxn]; 12bool vis[maxn]; 13int main() 14{ 15 std::ios::sync_with_stdio(false); 16 std::cin.tie(0); 17 std::cout.tie(0); 18 ll n,d,k; 19 cin>>n>>d>>k; 20 for(int i=1;i<=n;i++){ 21 cin>>my[i].name>>my[i].money; 22 } 23 sort(my+1,my+1+n,[](node a,node b){ 24 return a.money>b.money; 25 }); 26 ll ans=0,num=0; 27 for(int i=1;i<=k;i++){ 28 ans+=my[i].money; 29 vis[i]=true; 30 num++; 31 if(ans>=d)break; 32 } 33 if(ans<d)cout<<"impossible"<<endl; 34 else{ 35 cout<<num<<endl; 36 for(int i=1;i<=n;i++){ 37 if(vis[i]) 38 cout<<my[i].name<<", YOU ARE FIRED!"<<endl; 39 } 40 } 41 return 0; 42}