欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)

程序员文章站 2022-05-09 22:54:32
...

题目链接

A. Make a triangle!

题意

让某段最少增加多少使得构成三角形

思路

让较小两段往最长段去凑

代码

#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl;
using namespace std;

int a[5];

int main(){
    scanf("%d%d%d",&a[1],&a[2],&a[3]);
    sort(a+1,a+1+3);
    if(a[1]+a[2] > a[3])puts("0");
    else printf("%d\n",a[3]-a[2]-a[1]+1);
    return 0;
} 

B. Equations of Mathematical Magic

题意

存在多少种$x$使得$x$与$a$满足题式

思路

打表发现与$a$的二进制表示中$1$的数量有关

代码

#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl;
using namespace std;
typedef long long LL;

int t,n;
LL pw[35];

int main(){
    scanf("%d",&t);
    pw[0]=1;
    for(int i=1;i<35;i++)pw[i]=2LL*pw[i-1];
    while(t--){
        scanf("%d",&n);
        int cnt=0;
        for(int i=0;i<=31;i++)if((1<<i)&n)cnt++;
        printf("%lld\n",pw[cnt]);
    }
    return 0;
}

C. Oh Those Palindromes

题意

用原串字符构造出子串中回文串最多的串

思路

让相同字符相邻必定为最优情况

代码

#include <bits/stdc++.h>
#define cerr << #x << " = " << x << endl;
const int maxn = 1e5+5;
using namespace std;

int n,cnt[30];
char s[maxn];

int main(){
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++)cnt[s[i]-'a']++;
    for(int i=0;i<26;i++){
        for(int j=0;j<cnt[i];j++)printf("%c",i+'a');
    }puts("");
}

D. Labyrinth

题意

从某点出发,左右移动次数有限,最多能到达几个合法点

思路

优先进行上下移动,用双端队列模拟bfs

代码

#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl;
const int maxn = 2e3+5;
using namespace std;

int n,m,sr,sc,lm,rm;
int tot,vis[maxn][maxn];
int tr[4]={1,-1,0,0},tc[4]={0,0,1,-1};
char mp[maxn][maxn];

struct node{
    int r,c,t1,t2;
};

void bfs(){
    deque<node>Q;
    vis[sr][sc]=1;
    Q.push_back({sr,sc,lm,rm});
    while(!Q.empty()){
        node tmp=Q.front();
        Q.pop_front();
        for(int i=0;i<4;i++){
            node now=tmp;
            now.r+=tr[i],now.c+=tc[i];
            if(now.r >= 1 && now.r <= n && now.c >= 1 && now.c <= m && !vis[now.r][now.c] && mp[now.r][now.c] == '.'){
                if(i < 2){tot+=vis[now.r][now.c]=1;Q.push_front({now.r,now.c,now.t1,now.t2});}
                else{
                    if(tc[i] == -1 && now.t1){
                        tot+=vis[now.r][now.c]=1;
                        Q.push_back({now.r,now.c,now.t1-1,now.t2});
                    }
                    if(tc[i] ==  1 && now.t2){
                        tot+=vis[now.r][now.c]=1;
                        Q.push_back({now.r,now.c,now.t1,now.t2-1});
                    }
                }
            }
        }
    }
}

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&sr,&sc,&lm,&rm);
    for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);
    bfs();
    printf("%d\n",tot+1);
    return 0;
}

E. Dwarves, Hats and Extrasensory Abilities

题意

交互题,每次询问一个点的颜色,最后用一条直线将两种颜色的点分开,不存在这种直线也会WA

思路

先询问坐标上的点,二分枚举剩余点,颜色与第一点相同就$l=mid$,否则$r=mid$,等于把与第一点相同色的点分在一边,剩下的分在另一边

代码

#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl;
const int maxn = 35;
using namespace std;

int n;
string str[maxn];

int main(){
    cin >> n;
    cout << "0 2\n";
    fflush(stdout);
    cin >> str[1];
    int l=1,r=(int)1e9,mid;
    for(int i=2;i<=n;i++){
        mid=(l+r)/2;
        cout << mid << ' ' << 2 << endl;
        fflush(stdout);
        cin >> str[i];
        (str[i][0] == str[1][0]) ? l=mid : r=mid;
    }
    cout << l << ' ' << 3 << ' ' << r << ' ' << 1 << endl;
    fflush(stdout);
    return 0;
}

F. Candies for Children

留坑,寒假补