Problem A All Palindrome

https://ac.nowcoder.com/acm/contest/624/A

题解:这个字符串只能是所有字符相同的

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str[N];
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    cin>>str;
    for(int i=0;i<n;i++){
        a[str[i]-'a']++;
    }
    for(int i=0;i<26;i++){
        ans=max(ans,a[i]);
    }
    cout<<n-ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem B Clarifications

https://ac.nowcoder.com/acm/contest/624/B

题解:

C++版本一

#include<bits/stdc++.h>
using namespace std;
int n,p;
int vis[10000]={0};
string pp[110],ss[10000];
int main(){
    cin>>n>>p;
        getchar();
    for(int i=0;i<p;i++)
    {
        getline(cin,pp[i]);
    }
 
    for(int i=0;i<n;i++)
    {
        getline(cin,ss[i]);
 
        if(ss[i][ss[i].size()-1]=='.'){
            printf("No Response.\n");
            continue;
        }
        int flag=0;
        for(int j=0;j<p;j++)
        {
            if(ss[i]==pp[j])
            {
                printf("42.\n");
                flag=1;
                break;
            }
        }
        if(flag)continue;
        vis[i]=1;
        for(int j=i-1;j>=0;j--)
        {
            if(ss[j]==ss[i]){
                vis[i]=vis[j]+1;
                break;
            }
        }
        if(vis[i]<=5)printf("Read the problem statement carefully.\n");
        else printf("Juries are investigating. Thanks.\n");
    }
     
    return 0;
}

Problem C 

https://ac.nowcoder.com/acm/contest/624/C

题解:模拟

1、暴力查找n所在的数是几位数

2、n所在的数是1中确定的几位数的第几个

3、n是2确定的数的第几位

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
ll power(ll a ,ll b){
    ll res=1;
    ll base=a;
    while(b){
        if(b&1)res=res*base;
        base=base*base;
        b>>=1;
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);

        ll l=0;
        ll r=9;
        cnt=1;
        while(1){
            if(l<n&&n<=r)
                break;
            l=r;
            cnt++;
            r=r+9*power(10,cnt-1)*cnt;
        }
        //cout<<l<<" "<<r<<endl;
        ll L=1;
        ll R=9*power(10,cnt-1);
        ans=1;
        while(L<=R){
            ll mid=(L+R)>>1;//cout<<L<<" "<<R<<endl;
            if(l+(mid-1)*cnt<n&&n<=l+(mid)*cnt){
                ans=mid;
                break;
            }else if(l+(mid-1)*cnt>=n){
                R=mid-1;
            }else{
                L=mid+1;
            }
        }
        //cout<<ans<<endl;
        ll num=power(10,cnt-1)+ans-1;
        l=l+(ans-1)*cnt;
        //cout<<num<<endl;
        ans=n-l;
        ans=num/(ll)power(10,cnt-ans)%10;
        cout<<ans<<endl;

    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem G Virtual Youtuber

https://ac.nowcoder.com/acm/contest/624/G

题解:差分法

求相反

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
ll a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%lld",&t);
    int T=0;
    while(t--){
        scanf("%lld%lld",&n,&p);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        l=1;
        r=1;
        ans=0;
        temp=a[1];
        while(r<=n){
            //cout<<l<<" "<<r<<" "<<temp<<endl;
            if(temp>=p){
                ans+=n-r+1;
                temp-=a[l++];
            }else{
                temp+=a[++r];
            }
        }
        cout<<"Case #"<<++T<<": "<<n*(n+1)/2-ans<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem J Bubble Sort

https://ac.nowcoder.com/acm/contest/624/J

题解:乘法逆元 规律

1、交换次数的权呈现正态分布;

2、最少交换次数0,最多交换次数n(n-1)/2;

3、根据数列求和可知答案为n(n-1)/4;

4、费马小定理

5、快速幂

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=998244353;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
ll power(ll a ,ll b,ll c){
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        printf("%lld\n",((((n%MOD)*((n-1)%MOD))%MOD)*power(4,MOD-2,MOD))%MOD);
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}