Codeforces Round 883 (Div. 3)---暑假刷题Day7（A~F2,G）

A - Rudolph and Cut the Rope 

        题意：n个钉子钉在墙上，高度为hi,有一根绳子挂在上面，长度为si，同时绳子的另一端绑着一个球。求切断多少根绳子球能落地。

        思路：从结果来看，最终绳子长度大于等于钉子高度的绳子不需要切断，其余都需要切断

void solve() 
{int n;cin>>n;int cnt = 0;for(int i = 0 ; i < n ;  i++){int a , b;cin>>a>>b;if(a > b)cnt++;}	cout<<cnt<<endl;
}     

B.Rudolph and Tic-Tac-Toe

        题意：三人井字棋，判断谁胜利

        思路：模拟即可

void solve() {int map[3][3];memset(map,0,sizeof map);for(int i = 0;  i< 3 ; i ++){string s;cin>>s;for(int j = 0 ; j < 3 ; j ++){if(s[j] == '+'){map[i][j] = 0;}else if(s[j] == 'X'){map[i][j] = 1;}else if(s[j] =='O'){map[i][j] = 2;}else map[i][j] = -1;}}int k = -1;for(int i = 0 ; i < 3 ; i++){if(map[i][0] == map[i][1] && map[i][0] == map[i][2]){k = max(k,map[i][0]);}if(map[0][i] == map[1][i] && map[0][i] == map[2][i]){k = max(k,map[0][i]);}}if(map[0][0] == map[1][1] && map[0][0] == map[2][2]){k = max(k,map[0][0]);}if(map[2][0] == map[1][1] &&map[2][0] == map[0][2]){k = max(k,map[1][1]);}if(k == -1){cout<<"DRAW\n";}else{if(k == 1){cout<<'X'<<endl;}else if(k == 0){cout<<'+'<<endl;}elsecout<<'O'<<endl;}
}            

C - Rudolf and the Another Competition 

        题意：有n道题目，m个人，ICPC赛制，每个人每道题所花费的时间给出，求最优情况下的最终第一个人的排名。

        思路：贪心，每个人每道题所花费的时间从小到大排序一下，最后求出得分和总时间，再排个序即可。（这题没用LL被Hack了）

struct Node{int point = 0;LL time = 0;int id;
};
int cmp1(Node a, Node b){if(a.point != b.point){return a.point>b.point;}else if(a.time != b.time){return a.time < b.time;}else{return a.id < b.id;}
}
int cmp(int a , int b){return a<b;
}
void solve() 
{int n , m, h;cin>>n>>m>>h;Node peop[n];for(int i = 0 ; i < n  ; i++){peop[i].id = i;int num[m];for(int j = 0 ; j < m ; j ++){cin>>num[j];}sort(num , num + m , cmp);int ti = h;int idx = 0;int cost = 0;int t = 0;while(1){if(idx >= m)break;if(ti >= num[idx]){t += num[idx];ti -= num[idx];cost += t;idx++;}else{break;}}peop[i].time = cost;peop[i].point = idx;}sort(peop , peop + n , cmp1);for(int i = 0 ; i< n ; i++){if(peop[i].id == 0){cout<<i+1<<endl;break;}}
}            

D - Rudolph and Christmas Tree

        题意：给定三角形的底和高，假设有n个三角形和一个轴，每个三角形的底都垂直于轴，给出每个三角形与轴的交点坐标，求整个图形的面积。

        思路：写个求面积函数即可。

double cntS(double d , double h , double h1 , double h2){double k = min(h2 - h1 , h);double jian = d*1.0/h;double top = d - k * jian;double cnt = (d + top) * k / 2;return cnt;
}
void solve() 
{int n;cin>>n;double d , h;cin>>d>>h;double hei[n];for(int i = 0 ; i< n ; i++){cin>>hei[i];}sort(hei , hei + n , cmp);double S1 = d * h / 2;double ans = S1;for(int i = 0 ; i < n - 1; i++){ans += cntS(d,h,hei[i],hei[i+1]);}printf("%.08f\n" , ans);
} 

E2 - Rudolf and Snowflakes (hard version) 

        题意：给定一个n，判断能否找到一对x，y使得。

        思路：（观摩别人代码找到的思路）由等比数列求和公式得到 , 由此再判断的时候只需要将 ,再判断 n 是否能一直被x整除即可。那么如何找到这个x，由于,所以 。我们只需要对y可能的取值进行遍历即可。由于,所以只需要对每一个y ， 找到刚好能使得一个x使得 且 ，并判断 能否一直被x整除即可。
       

LL max_x(LL x , int y){LL max = pow(x , (long double)1.0/y);while(pow(max,y) <= x){max++;}max--;return max;
}
void solve() 
{LL n;cin>>n;for(int y = 2 ; y < 64 ; y ++){LL k = max_x(n,y);if(k < 2)continue;__int128 nn = n;nn *= (k - 1);nn += 1;while(nn % k == 0)nn/=k;if(nn == 1){cout<<"YES"<<endl;return;}}cout<<"NO"<<endl;
}            

 G - Rudolf and CodeVid-23 

        题意：有n种传染病，给定一个长度为n的01串，其中0表示没有生第i种病，1表示生第i中病。有m种药，每个药有三个属性：时间，作用，副作用。其中时间表示了这种药需要吃几天，作用和副作用都是长度为n的串，其中作用串中的1表示吃了以后该种病痊愈，副作用的1表示吃完以后生了该种病。求能够痊愈的方案中时间最短的那个。
        思路：状态压缩，对于每一种药来说，假设当前状态为 x , 药的作用为y，副作用为z。假设第k种病，只有当 x >> k & 1 == 1 && y >> k & 1 == 0 时才不能治愈 ， 同样只有当 x >> k & 1 == 0 && z >>k & 1 == 0 是，才不会染上这种病。因此吃完药之后状态转移为 x & (~y) | z  DP[i]表示 i 状态下的最短时间，由此状态转移方程  。由于不同药顺序不同会影响结果，所以需要重复多次（最坏情况下会TLE或者WA）

struct Node{int pure;int il;int time;
};
int dp[1 << 11];
void solve() 
{int n , m ;cin>>n>>m;for(int i = 0 ; i < 1 << 11 ; i ++){dp[i] = INF;}int ill = 0;string s;cin>>s;for(int i = 0 ; i < n ; i++){if(s[i] == '1'){ill += pow(2,i);}}Node yao[m];dp[ill] = 0;for(int i = 0; i < m ; i++){int t = 0;cin>>t;string s1 ,s2;cin>>s1>>s2;int b = 0, c = 0 , d = 0;for(int j = 0;  j < n ; j ++){if(s1[j] == '1')b += pow(2,j);if(s2[j] == '1')c += pow(2,j);}b = b ^ ((1 << n) - 1);yao[i].time = t;yao[i].pure = b;yao[i].il = c;}int minn = INF;for(int k = 0 ; k < 100 ; k ++){for(int i = 0 ; i < m ; i ++){for(int j = 1 ; j < 1 << n; j ++){int b = yao[i].pure , c = yao[i].il , t = yao[i].time;int mask = j & b | c;dp[mask] = min (dp[mask] , dp[j] + t);}			}for(int i = m -1 ; i >=0 ; i --){for(int j = 1 ; j < 1 << n; j ++){int b = yao[i].pure , c = yao[i].il , t = yao[i].time;int mask = j & b | c;dp[mask] = min (dp[mask] , dp[j] + t);}			}}if(dp[0] != INF)cout<<dp[0]<<endl;elsecout<<"-1"<<endl;
}