Codeforces ラウンド #242 (ディビジョン 2) _html/css_WEB-ITnose

CF424 A. スクワット

タイトルの意味:

x と X は n (n は偶数) あります。X の数が n/2 となる最小の変換回数を求め、変換されたシーケンスを出力します。

問題解決のアイデア:

X の数を数えて、それを n/2 と比較します。それが小さい場合は、n/2-ans x を x に変更する必要があります (前から順にスキャンするだけです)。戻る）。

コード:

//#include<CSpreadSheet.h>#include<iostream>#include<cmath>#include<cstdio>#include<sstream>#include<cstdlib>#include<string>#include<string.h>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#include<bitset>#include<cmath>#define eps 1e-6#define INF 0x3f3f3f3f#define PI acos(-1.0)#define ll __int64#define LL long long#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#define M 1000000007//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;char save[220];int n;int main(){   //freopen("in.txt","r",stdin);   //freopen("out.txt","w",stdout);   while(~scanf("%d",&n))   {       int ans=0;       scanf("%s",save+1);       for(int i=1;i<=n;i++)            if(save[i]=='X')                ans++;       printf("%d\n",abs(n/2-ans));       if(ans<n/2)       {           int cnt=0;           for(int i=1;i<=n;i++)           {               if(cnt>=(n/2-ans))               {                   printf("%c",save[i]);                   continue;               }               if(save[i]=='x')               {                   cnt++;                   printf("X");               }               else                    printf("X");           }       }       else       {           int cnt=0;           for(int i=1;i<=n;i++)           {               if(cnt==(ans-n/2))               {                   printf("%c",save[i]);                   continue;               }               if(save[i]=='X')               {                   cnt++;                   printf("x");               }               else                    printf("x");           }       }       putchar('\n');   }   return 0;}

CF 424B. Megacity

タイトルの意味:

中心都市、n 個の周囲都市の座標 (0,0) と人口を与えて、n 個の都市の人口と位置座標を教えてください。都市を中心に、総人口が 1,000,000-s を超える最小の半径を見つけます。

問題解決のアイデア:

まず各都市と中心都市の間の距離を求め、次に距離を並べ替えます。小さいものから大きいものへと順番にスキャンし、要件が満たされている場合は、終了して最小の半径を出力します。

コード:

//#include<CSpreadSheet.h>#include<iostream>#include<cmath>#include<cstdio>#include<sstream>#include<cstdlib>#include<string>#include<string.h>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#include<bitset>#include<cmath>#define eps 1e-6#define INF 0x3f3f3f3f#define PI acos(-1.0)#define ll __int64#define LL long long#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#define M 1000000007//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxn 1100struct Point{    double x,y;    double dis;    int v;}pp[Maxn];int n,s;int dp[Maxn];bool cmp(struct Point a,struct Point b){    return a.dis<b.dis;}int main(){   //freopen("in.txt","r",stdin);   //freopen("out.txt","w",stdout);   while(~scanf("%d%d",&n,&s))   {       for(int i=1;i<=n;i++)       {           double x,y;           scanf("%lf%lf%d",&x,&y,&pp[i].v);           pp[i].x=x;           pp[i].y=y;           pp[i].dis=sqrt(x*x+y*y);       }       sort(pp+1,pp+n+1,cmp);       /*for(int i=1;i<=n;i++)            printf("i:%d %lf\n",i,pp[i].dis);*/       double ans;       if(s>=1000000)       {           printf("0\n");           continue;       }       int lef=1000000-s;       int i=1;       while(lef>0&&i<=n)       {           ans=pp[i].dis;           lef-=pp[i].v;           i++;       }       if(lef>0)       {           printf("-1\n");           continue;       }       printf("%lf\n",ans);   }   return 0;}

CF 424C. 魔法の公式

タイトルの意味:

円周率が与えられたとき、Q を求めます。

問題解決のアイデア:

または、演算が交換法則と結合法則を満たす。

元の式は、最初にすべての pi を OR 演算し、次に各 i (1=

Preprocess dp[i]=1^2^3..^i

コード:

//#include<CSpreadSheet.h>#include<iostream>#include<cmath>#include<cstdio>#include<sstream>#include<cstdlib>#include<string>#include<string.h>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<ctime>#include<bitset>#include<cmath>#define eps 1e-6#define INF 0x3f3f3f3f#define PI acos(-1.0)#define ll __int64#define LL long long#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1#define M 1000000007//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define Maxn 1100000int dp[Maxn];int n;void init(){    dp[0]=0;    for(int i=1;i<=1000000;i++)        dp[i]=dp[i-1]^i;}int main(){   //freopen("in.txt","r",stdin);   //freopen("out.txt","w",stdout);   init();   while(~scanf("%d",&n))   {       int ans=0;       for(int i=1;i<=n;i++)       {           int p;           scanf("%d",&p);           ans=ans^p;           if((n/i)&1) //ÆæÊý           {               ans=ans^dp[i-1];           }           ans=ans^dp[n%i];       }       printf("%d\n",ans);   }   return 0;}