A. Good ol’ Numbers Coloring 判断2个数是否互质就行了

AC代码

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; const int man = 2e5+10; #define IOS ios::sync_with_stdio(0) template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);} template<typename T>T exgcd(T a,T b,T &g,T &x,T &y){if(!b){g = a,x = 1,y = 0;}else {exgcd(b,a%b,g,y,x);y -= x*(a/b);}} #ifndef ONLINE_JUDGE #define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");} #else #define debug(fmt, ...) #endif typedef long long ll; const ll mod = 1e9+7; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt","w",stdout); #endif int t;cin >> t; while(t--){ int a,b; cin >> a>> b; if(gcd(a,b)!=1)cout << "Infinite" << endl; else cout << "Finite" <<endl; } return 0; }

B. Restricted RPS 题意：石头剪刀布的规则，给你一个字符串只包含‘R’,‘P’,'S’三种字符， R：石头 P：布 S：剪刀 然后有a个石头，b个布，c个剪刀 让你赢的局数大于等于ceil(n/2)(向上取整)

思路：一次匹配，有能赢的就赢，不能赢的先放着不管，最后在把剩余的随便分给先前没管的。

AC代码

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; const int man = 2e5+10; #define IOS ios::sync_with_stdio(0) template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);} template<typename T>T exgcd(T a,T b,T &g,T &x,T &y){if(!b){g = a,x = 1,y = 0;}else {exgcd(b,a%b,g,y,x);y -= x*(a/b);}} #ifndef ONLINE_JUDGE #define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");} #else #define debug(fmt, ...) #endif typedef long long ll; const ll mod = 1e9+7; map<char,int>mp; map<char,char>dui; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt","w",stdout); #endif int t;cin >>t; dui['R'] = 'P';dui['P'] = 'S';dui['S'] = 'R'; while(t--){ int n;cin >> n; int a,b,c; cin >> a>> b >> c; mp['R'] = a;mp['P'] = b;mp['S'] = c; string s;cin >> s; int ans = 0; char res[110]; memset(res,0,sizeof(res));//注意每次对res清零，无脑贡献2发罚时. for(int i = 0;i < s.size();i++){ if(mp[dui[s[i]]]>0){ ans++; mp[dui[s[i]]]--; res[i] = dui[s[i]]; } } for(int i = 0;i < n;i++){ if(res[i]!='R'&&res[i]!='S'&&res[i]!='P'){ if(mp['S']>0)res[i] = 'S',mp['S']--; else if(mp['R']>0)res[i] = 'R',mp['R']--; else if(mp['P']>0)res[i] = 'P',mp['P']--; } } res[n] = '\0'; n = ceil(1.0*n/2); if(ans>=n)cout << "YES\n",cout << res << endl; else cout << "NO\n"; } return 0; }

C. Constanze’s Machine 题意：原序列中的m会变成nn，w会变成vv；形成最终序列 现在给你最终序列，求原序列有多少种。

思路：首先要组成m或w，肯定要连续的nn或vv，那我们就来看长度为n的vv有多少种情况。 考虑dp，dp[i]表示前i个位置的组合情况，对于当前位置，要么自己单独，要么与前一个n组成一个m，所以dp[i] = dp[i-1] + dp[i-2] 。dp[0] = 1,dp[1] = 1; (其实列举几个出来就会发现就是一个fib数列)

每段连续的求出来了，乘起来就是答案，注意取模.

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; const int man = 2e5+10; #define IOS ios::sync_with_stdio(0) template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);} template<typename T>T exgcd(T a,T b,T &g,T &x,T &y){if(!b){g = a,x = 1,y = 0;}else {exgcd(b,a%b,g,y,x);y -= x*(a/b);}} #ifndef ONLINE_JUDGE #define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");} #else #define debug(fmt, ...) #endif typedef long long ll; const ll mod = 1e9+7; int dp[man]; void init(int n){ dp[1] = dp[0] = 1; for(int i = 2;i <= n;i++){ dp[i] = (dp[i-1] + dp[i-2])%mod; } } vector<int>res; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt","w",stdout); #endif string s; cin >> s; init(s.size()); int len = s.size(); bool f = 0; for(int i = 0;i < len;i++){ if(s[i]=='w'||s[i]=='m')f = 1; if(s[i]=='u'||s[i]=='n'){ int le = 1;int j; for(j = i+1;j < len;j++){ if(s[j]==s[i])le++; else break; } i = j-1; res.push_back(le); } } if(f)cout << "0" << endl; else{ ll ans = 1; for(int i = 0;i < res.size();i++){ ans = (ans*dp[res[i]])%mod; } cout << ans << endl; } return 0; }

D. Shichikuji and Power Grid 题意：n个笛卡尔坐标上的点，每个点有一个ci，ki，现在需要全部点通电，可以在该点建发电站，也可以连接其他发电站，在每个点建发电站的花费为ci，连接其他点的花费为两点的曼哈顿距离*两点k之和。求花费最小。

思路：建图，跑最小生成树。为什么这样做？首先我们每个点都要通电且花费最小，很明显最小生成树。 建图：一个超级源点连接n个点，边权为ci，表示这个点是否做发电站，然后每个点与其他点连一条边，权值为连接边的花费。 用prime算法跑生成树，结构体记录当前点的前驱结点，用来保存答案

AC代码

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; const int man = 2e3+10; #define IOS ios::sync_with_stdio(0) template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);} template<typename T>T exgcd(T a,T b,T &g,T &x,T &y){if(!b){g = a,x = 1,y = 0;}else {exgcd(b,a%b,g,y,x);y -= x*(a/b);}} #ifndef ONLINE_JUDGE #define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");} #else #define debug(fmt, ...) #endif typedef long long ll; ll inf = 1e18; const ll mod = 1e9+7; struct node{ int x,y; int c,k; }a[man]; struct noe{ int u; ll dis; }; struct no{ int u,pre; ll dis; bool operator <(const no &a)const{ return dis > a.dis; } }; vector<noe>sp[man]; ll dis[man]; bool vis[man]; priority_queue<no>q; vector<pair<int,int> >res2; vector<int>res1; int n; void prim(int s){ for(int i = s;i <= n;i++)dis[i] = inf; memset(vis,false,sizeof(vis)); q.push(no{s,-1,0}); ll ans = 0; while(!q.empty()){ no tp = q.top();q.pop(); int u = tp.u; if(vis[u])continue; vis[u] = 1; ans += tp.dis; if(tp.dis!=0){ if(tp.pre==0)res1.push_back(u); else res2.push_back(make_pair(u,tp.pre)); } for(int i = 0;i < sp[u].size();i++){ int v = sp[u][i].u; ll diss = sp[u][i].dis; if(vis[v])continue; if(dis[v] > diss){ dis[v] = diss; q.push(no{v,u,dis[v]}); } } } cout << ans << endl; cout << res1.size() << endl; for(int i = 0;i < res1.size();i++){ cout << res1[i] << " " ; }cout <<endl; cout << res2.size() << endl; for(int i = 0;i < res2.size();i++){ cout << res2[i].first << " " << res2[i].second <<endl; } } signed main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt","w",stdout); #endif cin >> n; for(int i = 1;i <= n;i++)cin >> a[i].x >> a[i].y; for(int i = 1;i <= n;i++)cin >> a[i].c; for(int i = 1;i <= n;i++)cin >> a[i].k; int s = 0; for(int i = 1;i <= n;i++){ sp[s].push_back(noe{i,a[i].c}); sp[i].push_back(noe{s,a[i].c}); } for(int i = 1;i <= n;i++){ for(int j = i + 1;j <= n;j++){ ll dis = abs(a[i].x-a[j].x) + abs(a[i].y-a[j].y); sp[i].push_back(noe{j,1ll*dis*(a[i].k + a[j].k)}); sp[j].push_back(noe{i,1ll*dis*(a[i].k + a[j].k)}); } } prim(s); return 0; }

E: 题意：给你一个10*10的网格，要你从左下角走到左上角，奇数行只能向右走，偶数行向左走，遇到边界就向上。 每次的走的步数是由投掷骰子决定的，6种可能，概率相同，还有直达的，就是向上x行，但不能2次都连续2次直达， 问最少步数。

思路：很明显的一个期望dp，比赛时时间不够(还是太菜)，考虑把二维格子想成一条直线，然后楼梯关系对应一下， dp[i]表示离终点的最小期望步数,dp[100] = 0, 对于94-99情况比较特殊，因为会有自环， dp[i] = (dp[i]+1)*5/6 + (dp[100] + 1)/ 6 ⇒ dp[i] = 6 对于后面的，有2种决策，搭楼梯 or 投骰子 之间取一个min就好 $dp[i]={\sum }_{j=1}^{6}min((dp[i+j]+1)/6,(dp[t[i+j]+1)/6])$

java代码

import java.util.*; import java.io.*; public class Main{ static double dp[]; public static void main(String argv[]) throws IOException { StreamTokenizer in = new StreamTokenizer( new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int id[][] = new int[15][15]; int t[] = new int[110]; int num = 100; dp = new double[110]; for(int i = 1;i <= 10;i++) { int tp,p; if(i%2==0) { tp = 10;p = -1; }else { tp = 1;p = 1; } for(int j = 1;j <= 10;j++) { id[i][tp] = num--; tp += p; } } /*for(int i = 1;i <= 10;i++) { for(int j = 1;j <= 10;j++) { out.printf("%d ", id[i][j]); } out.printf("\n"); }*/ Arrays.fill(t, 0); for(int i = 1;i <= 10;i++) { for(int j = 1;j <= 10;j++) { int x;in.nextToken(); x = (int)in.nval; t[id[i][j]] = id[i-x][j]; //out.printf("%d ",t[id[i][j]]); } //out.printf("\n"); } dp[100] = 0.0; for(int i = 99;i >= 94;i--)dp[i] = 6.0; for(int i = 93;i >= 1;i--) { double ans = 0; for(int j = 1;j <= 6;j++) { ans += Math.min((dp[i+j]+1)/6.0,(1+dp[t[i+j]])/6.0); } dp[i] = ans; } out.printf("%.10f\n", dp[1]); out.close(); } }

F: 题意：一个区间[l，r]，问你这个区间有多少对数满足x + y = x ^ y ； 思路：很明显每位取的情况只有3种，{0 ，1} {1 ，0 } {0 ,0 } 先转化为2进制 考虑dp[i][][]表示前i位数x,y是否达到上限的组合数；

import java.util.*; import java.io.*; public class Main{ static final int man = 35+10; static long dp[][][]; static int x[],y[]; public static void main(String argv[]) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int t; in.nextToken(); t = (int)in.nval; while(t-->0) { int l,r; in.nextToken(); l = (int)in.nval; in.nextToken(); r = (int)in.nval; long ans = slove(r,r) - slove(l-1,r) - slove(r,l-1) + slove(l-1,l-1); out.println(ans); out.flush(); } out.close(); } static long slove(int a,int b) { if(a<0||b<0)return 0; int pos = 0; dp = new long[50][2][2]; x = new int[50]; y = new int[50]; for(int i = 0;i < 35;i++) { for(int j = 0;j < 2;j++) { for(int k = 0;k < 2;k++) { dp[i][j][k] = -1; //System.out.println(i + " " + j + " " + k); } } } while(a!=0||b!=0) { //System.out.println(pos + " " + a + " " + b); x[++pos] = a&1; y[pos] = b&1; a /= 2; b /= 2; } return dfs(pos,1,1); } static long dfs(int pos,int t1,int t2) { if(pos==0)return 1; if(dp[pos][t1][t2] != -1)return dp[pos][t1][t2]; long ans = 0; int up1 = t1==1 ? x[pos] : 1; int up2 = t2==1 ? y[pos] : 1; for(int i = 0;i <= up1;i++) { for(int j = 0;j <= up2;j++) { if(i==1&&j==1) continue; int a1 = 0,b1 = 0; if(t1==1&&i==up1)a1 = 1; if(t2==1&&j==up2)b1 = 1; ans += dfs(pos-1,a1,b1); } } dp[pos][t1][t2] = ans; return ans; } }