Codeforces Round 883 (Div. 3)
A. Rudolph and Cut the Rope：
题意：
有一个糖果由n个绳子悬挂，告诉每一个绳子位于的高度和宽度，问至少间断几根才可以让candy回到groud。
思路：
统计有几个宽度小于高度的绳子即可
void solve(){
int n;
int num=0;
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
if(x>y) num++;
}
cout<<num<<endl;
}
B. Rudolph and Tic-Tac-Toe：
题目： 给一个3X3的棋盘，上面是一些符号，一个符号连线长度为3就是赢家。输出赢家或者平局。
思路：模拟即可
void solve(){
char ch3='-';
for(int i=1;i<=3;i++){
char ch2;
bool flag=0;
for(int j=1;j<=3;j++){
cin>>ch[i][j];
if(j==1) ch2=ch[i][j];
else {
if(ch[i][j]!=ch2) flag=1;
}
if(j==3 && flag==0){
if(ch2!='.') ch3=ch2;
}
}
}
if(ch3!='-'){
cout<<ch3<<"\n";
return ;
}
else{
for(int j=1;j<=3;j++){
char ch2;
bool flag=0;
for(int i=1;i<=3;i++){
if(i==1) ch2=ch[i][j];
else {
if(ch[i][j]!=ch2) flag=1;
}
if(i==3 && flag==0 && ch2!='.'){
cout<<ch2<<"\n";
return ;
}
}
}
}
if(ch[1][1]==ch[2][2] && ch[2][2]==ch[3][3] && ch[2][2]!='.'){
cout<<ch[1][1]<<"\n";
return ;
}
if(ch[2][2]==ch[1][3] && ch[2][2]==ch[3][1] && ch[2][2]!='.'){
cout<<ch[2][2]<<"\n";
return ;
}
cout<<"DRAW"<<endl;
}
C. Rudolf and the Another Competition:
题目： 每一个人都在做题，已知每一个人做每一道题目所需要用的时间。在规定时间内进行排名：做题数目多的人排名高，其次是所用时间少的人排名高。问第一位玩家最后排名是第几？
思路： 对于每一个玩家做的每一道题目的时间进行排序，之后从小到大开始做就可以，因为数据比较小，直接暴力枚举就可以。如果数据范围比较大，可以用前缀和，最后二分前缀和找到做的题目的数量，并根据做题数目得到penalty。
代码：
struct node{
int id,number,tim;
}edge[200005];
bool cmp(node k,node kk){
if(k.number!=kk.number) return k.number>kk.number;
else return k.tim<kk.tim;
}
void solve(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
vector<int>p;
for(int i=1;i<=m;i++){
int x;
cin>>x;
p.push_back(x);
}
sort(p.begin(),p.end());
for(auto v:p){
if(v<=sum) {
now+=v;
summ+=now;
sum-=v;
num++;
}
else break;
}
edge[i]={i,num,summ};
}
sort(edge+1,edge+1+n,cmp);
for(int i=1;i<=n;i++){
if(edge[i].id==1) {
cout<<i<<"\n";
return ;
}
}
}
D. Rudolph and Christmas Tree:
题目： 有n个三角形，但是可能会出现覆盖的情况，最后要输出所有的三角形的面积之和。 如果出现了覆盖的情况，那么原先下面的一个三角形的形状就会变为梯形。
思路： 手推一下梯形的面积，并且运用相似的知识可以得到公式： 现在的竖直方向跨度/原先的h ==现在在水平方向上的跨度/（d/2)
由现在水平方向上的跨度就可以计算出来当前的梯形的面积。
void solve(){
int n;
cin>>n;
double d,h;
cin>>d>>h;
d=d/2.0;
for(int i=1;i<=n;i++){
cin>>loc[i];
}
loc[n+1]=0x3f3f3f3f;
double sum=d*h;
double ans=0.0;
for(int i=1;i<=n;i++){
if(loc[i+1]-loc[i]>=h){
ans+=sum;
}
else{
double h1=loc[i+1]-loc[i];
double d1=d-h1*d/h;
double s=(d1+d)*h1;
ans+=s;
}
}
printf("%.7lf\n",ans);
}
E. Rudolf and Snowflakes :
题目: 现在给出我们对于雪花的定义：
-
最中心是一个点，这个点连接k条边到第二层。
-
每一层的每一个点往下一层又拥有k条边。
-
至少有三层。
问给定结点数目，能否成为某一种雪花的结点数目。只需要输出yes/no。
思路： n最大是10的18次方。
第一层结点数目：1
第二层结点数目：k
第一层结点数目：k^2
第二层结点数目：k^3....
由此可以得到规律，如果给定的数字可以被上述公式的和表示出来，就是yes 否则就是no.
那么如何在规定时间内做到呢？考虑每一层有多少个满足条件的结果。
并且一定要至少为1+k^1+k^2
-
我们考虑总共只有3层的时候那么对于1e18的总结点数目，k可能为1e9
-
只有四层的时候对于1e18的总共数目，k最多也就是1e6
-
对于五层，k最多不到1e4.
-
如果我们把每一层的情况符合条件的都枚举出来，那么总共也就是最多到达第60层。
2的60次方就大于了10的18次方。
所以对于上述的在总共有3层~60层的情况，都可以直接存储下来。数目是1e6级别。 而对于第二层也就是1+k^1+k^2=n的情况，可以判断是否存在满足情况的东西。
代码：
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
const i64 maxn=1e18;
unordered_set<i64>S;
i64 AD(i64 a,i64 b){
if(maxn-a<b) return -1ll;
return a+b;
}
i64 mul(i64 a,i64 b){
if(a==-1 || b==-1 )return -1ll;
if(maxn/a<b) return -1ll;
return a*b;
}
bool solve(){
i64 n;
cin>>n;
if(n<5) return 0;
if(S.count(n)) return 1;
n-=1;
i64 q=sqrt(n);
if(mul(q,q+1)==n) return 1;
if(mul(q,q+1)==n || mul(q+1,q+2)==n) return 1;
return 0;
}
int main()
{
for(int num=4;num<=65;num++){
i64 k=2;
while(1){
i64 val=1;
i64 tmp=0;
bool flag=0;
for(int i=1;i<=num;i++){
if(val==-1) {
flag=1;
break;
}
tmp=AD(tmp,val);
val=mul(val,k);
}
if(tmp>=1 && tmp<=maxn && flag==0) S.insert(tmp);
else break;
k+=1;
}
}
int T;
cin>>T;
while(T--){
if(solve()) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
F. Rudolph and Mimic:
题目： 交互题，有n个物品，每一个都有自己的类型。里面有一个物品是很特殊的，除此之外的物品类型不会改变，这个物品的类型是会改变的。
操作：每一次直接输出:!+找到了这个物品的index；程序结束。 输出“- k"代表要删除k个数字，之后后面附带k个数，表示要删掉的数字的index。 之后会得到剩下的每一个物品的类型。
保证特殊物品不会连续3次都是一种类型。 每次删除之后得到的物品的类型，次序和上一次是可以随便调换的。
思路： 最开始，什么都不删除的情况下进行询问，一旦有一种类型的物品数目增加了，里面就一定会有特殊物品。 把其他的所有物品都删除掉之后再进行询问，直到剩下的物品里面出现了不同种类的，就是特殊物品。
代码：
void solve(){
memset(siz,0,sizeof(siz));
int n; int num=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
siz[a[i]]++;
}
cout<<"- 0"<<endl;
memset(siz1,0,sizeof(siz1));
for(int i=1;i<=n;i++){
cin>>a[i];
siz1[a[i]]++;
}
for(int i=1;i<=9;i++){
if(siz1[i]>siz[i]){
num=i;
break;
}
}
if(num==0){
cout<<"- 0"<<endl;
memset(siz1,0,sizeof(siz1));
for(int i=1;i<=n;i++){
cin>>a[i];
siz1[a[i]]++;
}
for(int i=1;i<=9;i++){
if(siz1[i]>siz[i]){
num=i;
break;
}
}
vector<int>p;
for(int i=1;i<=n;i++){
if(a[i]!=num) p.push_back(i);
}
cout<<"- "<<p.size();
for(auto v:p){
cout<<" "<<v;
}
int ans=0;
n-=p.size();
cout<<endl;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]!=num) ans=i;
}
if(ans!=0) {
cout<<"! "<<ans<<endl;
return ;
}
cout<<"- 0"<<endl;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]!=num){
ans=i;
}
}
if(ans!=0) cout<<"! "<<ans<<endl;
}
G. Rudolf and CodeVid-2：
题目： 有n种药品，然后m种病症。起初用一个二进制串表示自己的状态，某一位为1表示这一位的病症是的病状态，为0表示没有相应的病症。 每一张药都有自己可以作用的病症，以及副作用。每一种药都有自己的使用时间，问最后最短用多少时间可以让这个人达到健康状态？
思路： 总共最多之后10种病，那么也就只有1023种状态，用状态压缩。 用了一种药，再状态上进行相应的转换就可以。 相当于我们从当前状态到状态0的最短路，每一个点，都可以无限的使用其他的药。 最后如果能够到达状态0，就是可以，输出最短路，否则就不可以。 用set<pair<int,int> > 维护，dijikstra跑最短路即可。
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=2005;
int dat[N];
string t[N][3];
int used[N];
int tim[N];
void solve(){
memset(used,0,sizeof(used));
memset(tim,0x3f3f3f3f,sizeof(tim));
cin>>m>>n;
string beg;
cin>>beg;
for(int i=1;i<=n;i++){
cin>>dat[i]>>t[i][1]>>t[i][2];
}
set<pair<int,int> >s;//第一个是到达该状态所用的时间，第二个是状态本身。
int now=0;
for(int j=0;j<m;j++){
if(beg[j]=='1') now+=(1<<j);
}
s.insert({0,now});
while(s.size()!=0){
pair<int,int>tsk=*s.begin();
s.erase(tsk);
if(used[tsk.second]==1) continue;
used[tsk.second]=1;
tim[tsk.second]=min(tim[tsk.second],tsk.first);
for(int i=1;i<=n;i++){
int st=tsk.second;
for(int j=0;j<m;j++){
if(t[i][1][j]=='1' && (st&(1<<j))>0){
st-=(1<<j);
}
}
for(int j=0;j<m;j++){
if(t[i][2][j]=='1') {
st|=(1<<j);
}
}
s.insert({tsk.first+dat[i],st});
}
}
if(tim[0]<1e9) cout<<tim[0]<<endl;
else cout<<"-1\n";
}
int main()
{
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
标签：883,ch,return,cout,int,Codeforces,cin,i64,Div From： https://www.cnblogs.com/dhu-gxy/p/17537548.html