别问,问就是我真的很菜

2021ccpc女生赛模拟2,题目来源黑龙江2018ccpc省赛(女?)

只做出来三道题就开始划水了

A - A Count Task

求一个字符串中有多少个字串仅包含一种字符

当相同字符贴贴的时候(bushi),这是一个等差数列求和;而拒绝贴贴的时候,就是单纯+1

#include<iostream>
#include<string>
using namespace std;
typedef long long ll;

int main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        ll cnt=1;
        ll sum=0;
        for(int i=1;i<s.length();i++){
            if(s[i]==s[i-1]){
                cnt++;
            }
            else{
                sum+=((1+cnt)*cnt)/2;
                cnt=1;
            }
        }
        sum+=((1+cnt)*cnt)/2;
        cout<<sum<<endl;
    }
}

B - A Math Problem

给出n,求2n个不同的球放入n个盒子中的不同方式

题本身公式推导不难,但是2的64次方属实没想到什么好的处理方法

公式:
$$
\frac{C_{2n}^{2}\cdot C_{2n-2}^{2}\cdot\cdot\cdot C_{2}^{2}}{n}
$$
化简得到:
$$
\frac{(2n)!}{2^n\cdot n}
$$
然后代入计算咯..不过我并不会处理

C - A Path Plan

D - A Sequence Game

看着很像线段树

E - A Hard Allocation

非常简单,只可能是所有人都均等,或者相差1.鸽笼原理

#include<iostream>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        if(n%m==0) cout<<0<<endl;
        else{
            cout<<1<<endl;
        }
    }
}

F - Similar Strings

G - Flower

一直TLE,应该是一个Onlogn的算法来着..

H - Overflow

对不起优衣我划水了

I - Binary

J - The puzzle

看了下题解的思路,倒着算回去

因为一定能通过有限次操作使他回到1234..这样顺序的状态,所以设想他是如何从有序状态打乱的.

arr存数据,vis存是否访问

数组下标从1开始,从arr[1]进行遍历,若没有访问过,就temp=arr[temp],同时cnt++

2 3 4 1

2->3->4->1 ->2 此时cnt=4,cnt-1则是需要移动数据的次数

如果某个位置已经被访问过,此时cnt=0,不用管进行下一次循环

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
bool vis[maxn];
int arr[maxn];
void init(){
    memset(vis,false,sizeof(vis));
}
int main(){
    int t;
    cin>>t;
    while(t--){
        init();
        int n;cin>>n;
        for(int i=1;i<=n;i++){
            cin>>arr[i];
        }
        ll sum=0;
        for(int i=1;i<=n;i++){
            int temp=i,cnt=0;
            while(!vis[temp]){
                cnt++;
                vis[temp]=true;
                temp=arr[temp];
            }
            if(cnt) sum+=cnt-1;
        }
        cout<<sum<<endl;
    }
}