SDNU_ ACM_ ICPC_ 2022_ Winter_ Practice_ 4th [individual]

A

A - A Funny Game

The question ：n Coins in a circle , Each round can take away one or two adjacent coins , Finally, the player who takes all the coins wins .Alice First of all , Ask who will win .

Ideas ： When n<=2 when ,Alice You can take it all at once ,Alice A winning ; When n>=3 when , No matter what Alice take 1 or 2 individual ,Bob You can take coins according to the parity of the remaining coins , Cause to give Alice The number of coins left is even , thereafter ,Bob Just imitate Alice Take the coin ,Bob A winning .（ Symmetric game ）

#include <stdio.h>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <cstdlib>
#include <set>
#include <queue>
#define lowbit(x) x&(-x)
#define endl '\n'
#define sf(x) scanf("%d",&x)
#define rep(i,x) for(i=0;i<(x);i++)
#define gao(x) cerr<<#x<<"->"<<x<<endl
#define gen(x) x##_
typedef long long ll;
const int maxx=1e6+10;
using namespace std;

void solve()
{
    int n;
    while(cin>>n&&n)
    {
        if(n<=2) cout<<"Alice\n";
        else cout<<"Bob\n";
    }
}
int main()
{
    int _t=1;
    //scanf("%d",&_t);
    while(_t--)
    {
        solve();
    }
    system("pause");
}

D

D - Red and Blue

The question ： Here you are. n An element of r Array ,m An element of b Array , Without changing the relative position of the two array elements, it is merged into a Array , seek f(a) The maximum of

Ideas ： requirement a The maximum prefix sum of the array , because b and r The order of the array is independent , So we only need b The maximum prefix sum of the array plus r The maximum prefix sum of the array is the answer .

#include <stdio.h>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <cstdlib>
#include <set>
#include <queue>
#define lowbit(x) x&(-x)
#define endl '\n'
#define sf(x) scanf("%d",&x)
#define rep(i,x) for(i=0;i<(x);i++)
#define gao(x) cerr<<#x<<"->"<<x<<endl
#define gen(x) x##_
typedef long long ll;
const int maxx=110;
const int inf=0x3f3f3f3f;
using namespace std;
ll n,m;
ll a[maxx],b[maxx];
void solve()
{
    scanf("%lld",&n);
    ll maxa=0,maxb=0;
    ll suma=0,sumb=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        suma+=a[i];
        if(suma>maxa) maxa=suma;
    }
    scanf("%lld",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&b[i]);
        sumb+=b[i];
        if(sumb>maxb) maxb=sumb;
    }
    printf("%lld\n",maxa+maxb);
}
int main()
{
    int _t=1;
    scanf("%d",&_t);
    while(_t--)
    {
        solve();
    }
    system("pause");
}

F

F - The XOR Largest Pair 

The question ：

  Ideas ： Find the maximum XOR value of two numbers , Because XOR is No carry Addition of , It must be more A number of （ Note that not the biggest ） XOR with another number with the largest number of different bits under the binary . So take it out first The maximum number of binary digits The number of , Enumerate these numbers , XOR with other numbers , Keep taking the maximum .

#include <stdio.h>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <cstdlib>
#include <set>
#include <queue>
#define lowbit(x) x&(-x)
#define endl '\n'
#define sf(x) scanf("%d",&x)
#define rep(i,x) for(i=0;i<(x);i++)
#define gao(x) cerr<<#x<<"->"<<x<<endl
#define gen(x) x##_
typedef long long ll;
const int maxx=1e5+10;
const double PI=acos(-1);
const int inf=0x3f3f3f3f;
using namespace std;
int n;
ll a[maxx];
ll op[maxx];
ll ppow(ll n,ll m)
{
    ll ret=1;
    for(ll i=1;i<=m;i++)
    {
        ret*=n;
    }
    return ret;
}
void solve()
{
    scanf("%d",&n);
    ll ma=-inf;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(a[i]>ma) ma=a[i];// Take the maximum 
    }
    ll ans=-inf;
    int x=1.0*log(ma)/log(2);//x Is the number of bits of the maximum value under binary  x=log 2 ma   Rounding down 
    ll tem=ppow(2,x);//tem by x Minimum value under bit binary 
    int cnt=0;
    for(int i=1;i<=n;i++)// Take out the maximum number of binary digits 
    {
        if(a[i]>=tem)// Take out the maximum number of binary digits 
        {
            op[++cnt]=a[i];
        }
    }
    for(int i=1;i<=cnt;i++)// Enumerate the maximum number of binary digits 
    {
        for(int j=1;j<=n;j++)// enumeration a[j]
        {
            ll ret=op[i]^a[j];
            if(ret>ans) ans=ret;
        }
    }
    printf("%lld",ans);
}
int main()
{
    int _t=1;

    //scanf("%d",&_t);
    while(_t--)
    {
        solve();
    }
    system("pause");
}

I

I - Regular Bracket Sequence

The question ： Give you one containing ( and ), For the other ？ String , among ？ Can be replaced by ( or ), Ask if you can make a legal sequence .

Ideas ： First, the length of the string must be even , Second, just guarantee ） Not in the first place ,（ Not at the end .

#include <stdio.h>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <cstdlib>
#include <set>
#include <queue>
#define lowbit(x) x&(-x)
#define endl '\n'
#define sf(x) scanf("%d",&x)
#define rep(i,x) for(i=0;i<(x);i++)
#define gao(x) cerr<<#x<<"->"<<x<<endl
#define gen(x) x##_
typedef long long ll;
const int maxx=1e6+10;
using namespace std;
char s[110];
void solve()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    if(len&1)
    {
        printf("NO\n");
        return ;
    }
    if(s[1]==')'||s[len]=='(') printf("NO\n");
    else printf("YES\n");
}
int main()
{
    int _t=1;
    scanf("%d",&_t);
    while(_t--)
    {
        solve();
    }
    system("pause");
}

L 

L - : (Colon)

The question ： Give you the length of the hour hand and minute hand a,b, after h Hours ,m Minutes later , Find the length of the connecting line at the end of the hour hand and minute hand .

#include <stdio.h>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <list>
#include <cstdlib>
#include <set>
#include <queue>
#define lowbit(x) x&(-x)
#define endl '\n'
#define sf(x) scanf("%d",&x)
#define rep(i,x) for(i=0;i<(x);i++)
#define gao(x) cerr<<#x<<"->"<<x<<endl
#define gen(x) x##_
typedef long long ll;
const int maxx=110;
const double PI=acos(-1);
const int inf=0x3f3f3f3f;
using namespace std;
ll la,lb,h,m;
void solve()
{
    scanf("%lld %lld %lld %lld",&la,&lb,&h,&m);
    ll ta=0,tb=0;//min
    ta=h*60+m,tb=m;// Clockwise movement time , Minute hand movement time 
    double ang=(double)abs(12*tb-ta)/360.0;
    ang*=PI;// The angle of the two needles 
    printf("%.20f",sqrt(la*la+lb*lb-2*la*lb*cos(ang)));//a*a+b*b-c*c=2*a*b*cosC
}
int main()
{
    int _t=1;
    //scanf("%d",&_t);
    while(_t--)
    {
        solve();
    }
    system("pause");
}