湖南大学第十五届程序设计竞赛

Problem A Oshino Shinobu loves Mr.Donut

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

题意：

题解：

C++版本一

Problem B Kuangyeye's Resistance

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

题意：计算n级网络的等效电阻。

题解：

C++版本一

/*
*@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;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
ll POW(ll a,ll b=p-2,ll c=p){
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%p;
        base=(base*base)%p;
        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("%d",&t);
    //while(t--){
    scanf("%lld%lld%lld",&n,&r,&p);
    ll R=r;
    for(int i=2;i<=n;i++){
        R=(((R+2*r)%p*r%p)*((POW(R+3*r,p-2,p))%p))%p;
    }
    cout<<R<<endl;
    //}

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

Problem C One Piece

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

题意：二进制表示中找到1的数。

题解：__builtin_popcount

C++版本一

/*
*@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;
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);
        printf("%d\n",__builtin_popcount(n));
    }

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

Problem D Kth height

https://ac.nowcoder.com/acm/contest/908/D

题意：两只球队，都是n个人且都身高递增，m次操作，将p队的第q个人的身高变为t，并询问两只球队总集合中第k矮的那个人的身高，保证修改之后依然递增

题解：二分

C++版本一

题解：二分

1、二分出前k个人，在第一队里面有多少个；

2、注意多组数据；

3、二分范围[0,k];

/*
*@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,q;
int ans,cnt,flag,temp,sum;
int a[3][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("%d",&t);
    //while(t--){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)scanf("%d",&a[1][i]);
        for(int i=1;i<=n;i++)scanf("%d",&a[2][i]);
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d%d",&p,&q,&t,&k);
            a[p][q]=t;
            l=0;r=k;
            while(l<=r){
                int mid=(l+r)>>1;
                int temp=(upper_bound(a[2]+1,a[2]+n+1,a[1][mid])-a[2])-1;
                if(mid+temp<=k){
                    ans=mid;
                    l=mid+1;
                }else{
                    r=mid-1;
                }
            }
            cout<<max(a[1][ans],a[2][k-ans])<<endl;
        }
    }
    
    //}

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

Problem E Just calculat

https://ac.nowcoder.com/acm/contest/908/E

题意：

题解：

C++版本一

Problem F Cards with Numbers

https://ac.nowcoder.com/acm/contest/908/F

题意：

两个操作：

0 x（表示在包装盒中放入带有数字x的卡片。）
1 x（表示查询在包装盒中是否有号码为x的卡片。）

题解：

1、字典树

2、离散化+离线处理

C++版本一

题解：字典树

注意：数据原因可能还没最糟糕的情况所以卡过

/*
*@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=2500000+10;
const int M=1000+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,op;
int ans,cnt,flag,temp;
int a[N][10];
int en[N];
char x[20];
void insert(char *s){
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++){
        int ch=s[i]-'0';
        if(a[p][ch]==-1)a[p][ch]=++cnt;
        p=a[p][ch];
    }
    en[p]=1;
}
bool search(char* s){
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++){
        int ch=s[i]-'0';
        if(a[p][ch]==-1)
            return 0;
        p=a[p][ch];
    }
    return en[p];
}
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);
    memset(a,-1,sizeof(a));
    for(int i=1;i<=n;i++){
        scanf("%d%s",&op,x);
        if(!op){
            insert(x);
        }else{
            cout<<(search(x)?"yes":"no")<<endl;
        }
    }
    //}

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

C++版本二

题解：离散化+离线处理

Problem G Longest Palindrome Substring

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

题意：最长的回文子串的长度是否大于1

题解：枚举

C++版本一

/*
*@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=1;i<n-1;i++){
        if(str[i-1]==str[i+1]||str[i-1]==str[i]||str[i]==str[i+1]){
            ans=1;
            break;
        }
    }
    cout<<(ans||(n==2&&str[0]==str[1])?"YES":"NO")<<endl;
    //}

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

Problem H Longest Common Palindrome Substring

https://ac.nowcoder.com/acm/contest/908/H

题意：

题解：

C++版本一

Problem I Algorithm Choosing Mushrooms

https://ac.nowcoder.com/acm/contest/908/I

题意：给你n个篮子以及篮子里有的蘑菇，你可以取走一段连续的篮子，但这些篮子里的蘑菇总和必须是m的倍数，问你最多拿几只篮子？最多拿多少蘑菇？

题解：DP

C++版本一

题解：DP

1、记录每个余数第一次出现的位置；

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=200000+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;
ll ans,cnt,flag,temp,sum;
ll a[N];
ll b[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("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
        temp=a[i]%m;
        if(b[temp]==0)
            b[temp]=i;
        if((a[i]-a[b[temp]])%m==0){
            ans=max(ans,i-b[temp]);
            sum=max(sum,a[i]-a[b[temp]]);
        }
    }
    cout<<sum<<" "<<ans<<endl;
    //}

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

Problem J Simple Problem

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

题意：

题解：

C++版本一

Problem K Water Problem

https://ac.nowcoder.com/acm/contest/908/K

题意：

题解：

C++版本一