Codeforces Round #191 (Div. 2)

2023-01-27 10:01:13

在div 188中，幸运的达成了这学期的一个目标：CF1800+，所以这次可以打星去做div2，有点爽。

A.Flipping Game 直接枚举

B. Hungry Sequence 由于素数的分布大概10个中有一个，所以直接筛法筛1e5个即可。

C. Magic Five 删除串s中的某些字符，使得他整除5，并且跟删除顺序有关，现在问有k个串s连在一起组成一个新的串，问新的串有多少种删除方式。

我们可以先看每一个串，由于整除5的数的末尾只能为0或者5。

用样例二 13990作为说明。

考虑只有一个时，在13990中，只有第4位(从0开始算)，则前面有2^4中删除方式。

如果加上一个，即1399013990时，则删除方式有2^4+2^(4+5)。

如果再加上一个时，即139901399013990，则删除方式有2^4+2^(4+5*2)+2^(4+5*3)。

因此我们可以知道，如果单一一个串S中第i位（从0开始）为0或者5时，该串重复k次，则有

2^i+2^(i+|S|)+...+2^( i+|S|*(len-1) ) = 2^i * ( 2^0+2^len+2^(len*2)+...+2^(len*(n-1)) )

由于n,len都比较大，所以需要用到等比数列求和公式以及快速幂，可以化为

2^i * ( 2^(len*n)-1 ) / 2^len

因此这里的除法需要用到逆元。

于是这题可以解决。

D. Block Tower 只要在同一个连通块中，就可以从一个出发，把其他的所有城市人数上限置为200。

直接DFS一下，进去的时候，该地建100的城市，在DFS在该地结束时，如果该地是由其他城市来到，则直接拆掉该地，然后再把该地置为200。

E.待补。

代码：

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define debug puts("here")

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

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

#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)

#define pb push_back

#define RD(n) scanf("%d",&n)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)

#define All(vec) vec.begin(),vec.end()

#define MP make_pair

#define PII pair<int,int>

#define PQ priority_queue

/******** program ********************/

const int MAXN = 105;

int a[MAXN];

int n;

int cc(int x,int y){

    int ans = 0;

    for(int i=1;i<x;i++)

        ans += a[i];

    for(int i=x;i<=y;i++)

        ans += !a[i];

    for(int i=y+1;i<=n;i++)

        ans += a[i];

    return ans;

}

int main(){

#ifndef ONLINE_JUDGE

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

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

#endif

    while(cin>>n){

        int ans = 0;

        rep1(i,n)

            RD(a[i]);

        rep1(i,n)

            for(int j=i;j<=n;j++)

                ans = max(ans,cc(i,j));

        cout<<ans<<endl;

    }

	return 0;

}

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define debug puts("here")

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

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

#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)

#define pb push_back

#define RD(n) scanf("%d",&n)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)

#define All(vec) vec.begin(),vec.end()

#define MP make_pair

#define PII pair<int,int>

#define PQ priority_queue

/******** program ********************/

const int MAXN = 2e6+5;

vector<int> p;

bool use[MAXN];

void init(){

    for(int i=2;i<MAXN;i++)

        if(!use[i]){

            p.pb(i);

            for(int j=i+i;j<MAXN;j+=i)

                use[j] = true;

        }

}

int main(){

#ifndef ONLINE_JUDGE

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

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

#endif

    init();

    int n;

    while(cin>>n){

        rep(i,n)

            printf("%d ",p[i]);

        puts("");

    }

	return 0;

}

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define debug puts("here")

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

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

#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)

#define pb push_back

#define RD(n) scanf("%d",&n)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)

#define All(vec) vec.begin(),vec.end()

#define MP make_pair

#define PII pair<int,int>

#define PQ priority_queue

/******** program ********************/

const ll MOD = 1000000007;

ll pw(ll p, ll n){

    ll sum = 1;

    while(n > 0){

        if(n & 1)

            sum = (sum * p) % MOD;

        n >>= 1;

        p = p * p % MOD;

    }

    return sum;

}

void ex_gcd(ll a,ll b,ll &gcd,ll &x,ll &y){

    if(b==0){

        x = 1;

        y = 0;

        gcd = a;

    }else{

        ex_gcd(b,a%b,gcd,y,x);

        y -= x*(a/b);

    }

}

ll Inv(ll n){

    ll x,y,gcd;

    ex_gcd(n,MOD,gcd,x,y);

    return gcd==1 ? (x%MOD+MOD)%MOD : -1;

}

int main(){

#ifndef ONLINE_JUDGE

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

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

#endif

    string s;

    ll n;

    while(cin>>s>>n){

        ll len = s.size();

        ll ans = 0;

        rep(i,len)

            if(s[i]=='0'||s[i]=='5')

                ans += pw(2,i)*Inv( pw(2,len)-1 )%MOD*( pw(2,len*n)-1 )%MOD;

        cout<<(ans%MOD+MOD)%MOD<<endl;

    }

	return 0;

}

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define debug puts("here")

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

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

#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)

#define pb push_back

#define RD(n) scanf("%d",&n)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)

#define All(vec) vec.begin(),vec.end()

#define MP make_pair

#define PII pair<int,int>

#define PQ priority_queue

/******** program ********************/

const int MAXN = 505;

char s[MAXN][MAXN];

int n,m;

bool use[MAXN][MAXN];

struct node{

    char op;

    int x,y;

    node(){}

    node(char a,int b,int c):op(a),x(b),y(c){}

};

vector<node> vec;

int dx[] = {0,0,-1,1};

int dy[] = {1,-1,0,0};

bool out(int x,int y){

    return x<1||y<1||x>n||y>m;

}

void dfs(int x,int y,bool has){

    use[x][y] = true;

    bool ok = false;

    rep(i,4){

        int cx = dx[i]+x;

        int cy = dy[i]+y;

        if(!out(cx,cy)&&!use[cx][cy]&&s[cx][cy]=='.')

            ok = true;

    }

    if(!ok&&has){

        vec.pb( node('R',x,y) );

        return;

    }

    vec.pb( node('B',x,y) );

    rep(i,4){

        int cx = dx[i]+x;

        int cy = dy[i]+y;

        if( !out(cx,cy) && !use[cx][cy] && s[cx][cy]=='.'){

            dfs(cx,cy,true);

            ok = true;

        }

    }

    if(has){

        vec.pb( node('D',x,y) );

        vec.pb( node('R',x,y) );

    }

}

int main(){

#ifndef ONLINE_JUDGE

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

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

#endif

    int ncase = false;

    while(cin>>n>>m){

        vec.clear();

        ncase?puts(""):ncase = true;

        memset(use,false,sizeof(use));

        rep1(i,n)

            scanf("%s",s[i]+1);

        rep1(i,n)

            rep1(j,m)

                if(s[i][j]=='.' && !use[i][j])

                    dfs(i,j,false);

        cout<<vec.size()<<endl;

        foreach(i,vec)

            printf("%c %d %d\n",vec[i].op,vec[i].x,vec[i].y);

    }

	return 0;

}

码农公寓

相关文章