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の手順)
n個人が輪になって、n対数を入力して、各対数はi番目の人の後にどの二人がいるかを表していますが、二人の位置が分かりません.この輪を見つけさせます.出力のいずれか.
考え方:
まず表aを打って、i行目の後と後の後を示すのは何日ですか?n個のvectorを申請して、iと隣接する番号を記録して、dfsを記録します.
括弧文字列を入力して、一つの文字だけを変えます.いくつかの場所が変更された後、文字列の括弧が適法にマッチします.
考え方:文字列を巡回して、'('x++でないと、x--、x=2かx=-2の時だけ存在します.次は左から)は比べられません.
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