Summer training #3

A:给一个包含字母加号括号的序列要求你删除多余的括号然后输出 (待改)

#include <bits/stdc++.h>

#include <cstring>

#include <iostream>

#include <algorithm>

#define foror(i,a,b) for(i=a;i<b;i++)

#define foror2(i,a,b) for(i=a;i>b;i--)

#define EPS 1.0e-8

#define PI acos(-1.0)

#define INF 3000000000

#define MOD 1000000009

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define lson o<<1, l, m

#define rson o<<1|1, m+1, r

//using ll = long long;

//using ull= unsigned long long;

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que;

typedef long long ll;

char s[];

int final[],visit[];

stack<int> stack1,stack2;

bool check()

{

 int pop=;

 if(stack1.top()==)

 pop=;

 if(stack2.top()==)

 pop=;

 if(s[stack1.top()-]=='+'||s[stack1.top()-]=='(')

 pop=;

 return pop;

}

bool same()

{

return s[stack1.top()-]=='(';

}

int main()

{

 freopen("in.txt", "r", stdin);

 //freopen("out.txt", "w", stdout);

 while(scanf("%s",s)==)

 {

        //cout << s<<endl;

        int cnt=;

        mem(final,);

        mem(visit,);

        int len=strlen(s);

        for(int i=;i<len;i++)

        {

        if(s[i]=='(')

        {

        stack1.push(i);

        stack2.push();

        }

        else if(s[i]=='+')

        {

        if(!stack2.empty())

        {

        stack2.pop();

        stack2.push();

        }

        }

        else if(s[i]==')')

        {

        //cnt++;

        //cout << cnt<<" "<<stack1.size()<<endl;

        if((!check())&&i<=len-||s[i+]==')'||s[i+]=='+')

        {

        final[i]=;

        final[stack1.top()]=;

        //cout << stack1.top()<<endl;

        if(stack1.top()==&&i+<len&&same&&s[i+]==')')

        {

        int t1=stack1.top();

        stack1.pop();

        int t2=stack1.top();

        stack1.pop();

        t2=t1;

        stack1.push(t2);

        stack1.push(t1);

        }

        }

        stack1.pop();

        //cout << cnt<<" "<<stack1.size()<<endl;

        }

        }

        /*for(int i=len-1;i>=0;i--)

        {

        if(s[i]=='(')

        {

        final[i]=0;

        break;

        }

        }*/

        for(int i=;i<len;i++)

        {

                if(final[i])

                printf("%c",s[i]);

        }

        cout<<endl;

 }

  return ;

}

C:给你一个l r要求在这之间找出两个数使之按位或后的值最大

因为是或所以最大的那个数肯定是r 另外一个在l,r之间找 1<<i-(1<<i-now)<=r-1-l

#include <bits/stdc++.h>

#include <cstring>

#include <iostream>

#include <algorithm>

#define foror(i,a,b) for(i=a;i<b;i++)

#define foror2(i,a,b) for(i=a;i>b;i--)

#define EPS 1.0e-8

#define PI acos(-1.0)

#define INF 3000000000

#define MOD 1000000009

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define lson o<<1, l, m

#define rson o<<1|1, m+1, r

//using ll = long long;

//using ull= unsigned long long;

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que;

typedef long long ll;

int er[];

ll l,r;

int pop=;

ll anser1=;

void init(ll t)

{

 while(t>)

 {

   er[pop++]=t%;

   t=t/;

 }

}

void doit()

{

        for(int i=;i<pop;i++)

        {

                if(er[i]==)

                anser1+=1LL<<i;

        }

}

int main()

{

 //freopen("in.txt", "r", stdin);

 //freopen("out.txt", "w", stdout);

 int t;

 cin>>t;

 while(t--)

 {

        cin >> l >> r;

        anser1=,pop=;

        init(r);

        for(int i=;i<pop;i++)

        {

        if(er[i]==)

        anser1+=1LL<<i;

        else

        {

        if(r->=l+anser1)

        er[i]=;

        }

        }

        anser1=;

        doit();

        cout << anser1<<endl;

 }

  return ;

}

I:素因子分解+容斥原理

假设卡片上标号分别是a1, a2, ..., an, M，跳蚤跳对应号的次数分别为x1, x2, ..., xn，跳M个单位长度的次数是xn+1，那么要满足已知条件只需满足方程：

a1x1+a2x2+...+anxn+Mxn+1 = 1 有解，即：

gcd (a1, a2, ..., an, M) = 1，接下来对M进行素因子分解，然后排除公因子非1的情况即可。

如代码所示：

设g为公因子非1的情况数，f(i)表示有i个公因子的情况数，由容斥原理得：g = f(1) - f(2) + f(3) -... f(k)

#include <iostream>

using namespace std;

#define LL __int64  

int fac[], k, a[], n, m, x;

LL tp;  

LL my_pow (LL a, int b)     //计算a^b

{

    LL res = ;

    while (b--) res *= a;

    return res;

}  

void dfs (int pos, int cnt, int num)    //dfs得到卡片中n+1个数有num个公因子时的方法数

{

    if (cnt == num)

    {

        x = m;

        for (int i = ; i < cnt; i++)

            x /= a[i];                  //x/p表示[1,x]中有多少个数是p的倍数

        tp += my_pow (x, n);            //要选n个数，每个数有x种选择

        return ;

    }

    for (int i = pos; i < k; i++)

    {

        a[cnt] = fac[i];

        dfs (i+, cnt+, num);

    }

}  

void divide (int p)                     //分解素因子，fac存放p的所有素因子

{

    for (int i = ; i * i <= p; i++)

    {

        if (p % i == )

        {

            fac[k++] = i;

            p /= i;

            while (p % i == )

                p /= i;

        }

    }

    if (p > ) fac[k++] = p;

}  

int main()

{

    LL ans, g;

    int i;

    while (cin >> n >> m)

    {

        g = ;

        divide (m);

        for (i = ; i <= k; i++)         //g = f(1)-f(2)+f(3)-f(4)+...f(k)

        {

            tp = ;

            dfs (, , i);

            if (i & ) g += tp;

            else g -= tp;

        }

        ans = my_pow (m, n) - g;         //ans = m^n - g

        cout << ans << endl;

    }

    return ;

}

K:博弈论 2*3 3*2 2*2 是N 1*n n*1 是P

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

int dp[][];

int getsg(int w,int h){

    if(dp[w][h]!=-)return dp[w][h];

    bool vis[];

    memset(vis,,sizeof(vis));

    for(int i=;i<=w-i;i++){

        dp[i][h]=getsg(i,h);

        dp[w-i][h]=getsg(w-i,h);

        vis[dp[i][h]^dp[w-i][h]]=true;

    }

    for(int i=;i<=h-i;i++){

        dp[w][i]=getsg(w,i);

        dp[w][h-i]=getsg(w,h-i);

        vis[dp[w][i]^dp[w][h-i]]=true;

    }

    for(int i=;;i++)

    if(!vis[i])

    return dp[w][h]=i;

}

int main()

{

    int w,h;

    memset(dp,-,sizeof(dp));

    while(scanf("%d%d",&w,&h)!=EOF){

        if(getsg(w,h))printf("WIN\n");

        else printf("LOSE\n");

    }

    return ;

}

巴特西

Summer training #3

最新文章

热门文章