CF 529 div 3

1969 ワード

http://codeforces.com/contest/1095
C:
n,kを入力して、k個の2の任意の乗数(1,2,4,8,16.)を見つけることができますか?
考え方:
最初にサイズkの配列を開け、最初の値を1とします.このときsum=kです.マーク変数t=1を設定して、毎回2を掛けて、whilleを通じて循環的に判断します.sum+t<=nであれば、付けます.×2の手順)
#include 
#include 
const int maxn = 2e5+5;
using namespace std;

int main()
{
    int n,k;
    int a[maxn];
    cin>>n>>k;
    for(int i=1;i<=k;i++)
        a[i]=1;
    int sum=k;
    for(int i=k;i>=1;i--)
    {
        int t=1;
        while(sum+t<=n)
        {
            a[i]+=t;
            sum+=t;
            t*=2;
        }
    }
    if(sum==n)
    {
        cout<
D:
n個人が輪になって、n対数を入力して、各対数はi番目の人の後にどの二人がいるかを表していますが、二人の位置が分かりません.この輪を見つけさせます.出力のいずれか.
考え方:
まず表aを打って、i行目の後と後の後を示すのは何日ですか?n個のvectorを申請して、iと隣接する番号を記録して、dfsを記録します.
#include 
#include 
#include 
using namespace std;
const int maxn = 2*1e5+5;
int vis[maxn];
int a[maxn][2];
vector v[maxn];
void dfs(int x)
{
    vis[x]=1;
    cout<>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        a[i][0]=x;
        a[i][1]=y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    return 0;
}
E:
括弧文字列を入力して、一つの文字だけを変えます.いくつかの場所が変更された後、文字列の括弧が適法にマッチします.
考え方:文字列を巡回して、'('x++でないと、x--、x=2かx=-2の時だけ存在します.次は左から)は比べられません.
#include 

using namespace std;
const int maxn = 1e6+5;
char s[maxn];
int a[maxn];
int main()
{
    int n;
    int t=0,b=0;
    int x=0;
    cin>>n;
    cin>>s;
    for(int i=0; i=0; i--)
        a[i]=min(a[i],a[i+1]);
    for(int i=0; i