Codeforces Round #242 (Div. 2) _html/css_WEB-ITnose

CF424 A. Squats

Question meaning:

There are n (n is an even number) x and X. Find the minimum number of transformations so that the number of X is n /2, output the transformed sequence.

Problem-solving ideas:

Count the number ans of Change ans-n/2 X's into x. (just scan it from front to back).

Code:

//#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

Question meaning:

For a central city Coordinates (0,0) and population s, n surrounding cities, tell the population and location coordinates of n cities, find the smallest radius with the central city as the center, so that the total population exceeds 1000000-s.

Problem-solving ideas:

First find the distance between each city and the central city, then sort the distances from small to large, and then scan in sequence. If the requirements are met, exit and output the smallest radius.

Code:

//#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. Magic Formulas

Question meaning:

Given pi, find Q.

Problem-solving ideas:

Or the operation satisfies commutative law and associative law.

The original formula can be equivalent to ORing all pi first, and then for each i (1=

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

Code:

//#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;}