吉首大学2019年程序设计竞赛

Problem A SARS病毒

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

题意：

题解：

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;
ll ans,cnt,flag,temp,sum;
ll a[4][4],b[4][4];
char str[N];
struct node{};
void Matrix(ll a[4][4],ll b[4][4]){
    ll e[4][4];
    memset(e,0,sizeof(e));
    for(int i=0;i<4;i++){
        for(int j=0;j<=i;j++){
            for(int k=0;k<4;k++){
                e[j][i]=e[i][j]=(e[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            a[i][j]=e[i][j];
        }
    }
}
ll power(int k){
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(i==j)a[i][j]=1,b[i][j]=2;
            else if(i+j==3) a[i][j]=0,b[i][j]=0;
            else a[i][j]=0,b[i][j]=1;
        }
    }
    while(k){
        if(k&1)Matrix(a,b);
        Matrix(b,b);
        k>>=1;
    }
    return a[0][0];
}
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(~scanf("%s",str)){
        int len=strlen(str);
        temp=0;
        for(int i=0;i<len;i++){
            temp=(temp*10+str[i]-'0')%(MOD-1);
        }
        cout<<power(temp)<<endl;
    }

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

C++版本二

题解：费马小定理+快速幂+数学

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
string str;
ll qmi(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
int main()
{
    while(cin>>str)
    {
        ll k=0;
        for(int i=0;i<str.size();i++)    k=(k*10+str[i]-'0')%(p-1);
        cout<<(qmi(2,k-1)+qmi(4,k-1))%p<<endl;
    }
    return 0;
}

Problem B 干物妹小埋

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

题意：

题解：最长递增子序列+树状数组

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=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;
ll ans,cnt,flag,temp,sum;
int a[N],h[N],v[N],A[N];
char str;
struct node{};
ll tree[N];
void update(int x,ll val){
    while(x<=cnt){
        tree[x]=max(tree[x],val);
        x+=x&-x;
    }
}
ll query(int x){
    ll res=0;
    while(x){
        res=max(tree[x],res);
        x-=x&-x;
    }
    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("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),h[i]=a[i];
    sort(a+1,a+n+1);
    A[++cnt]=a[1];
    for(int i=2;i<=n;i++)if(a[i]!=a[i-1])A[++cnt]=a[i];
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
        ll id = lower_bound(A+1,A+cnt+1,h[i])-A;
        temp = query(id);
        ans = max(ans, temp + v[i]);
        update(id, temp + v[i]);
    }
    cout<<ans<<endl;
    //}

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

Problem C 

题意：

题解：

C++版本一

Problem D 

题意：

题解：

C++版本一

Problem E 多喝嘤料

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

题意：

题解：

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;
ll 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);
        ans=m=n;
        while(n/3||m/4){
            temp=n/3+m/4;
            n%=3;
            m%=4;
            n+=temp;
            m+=temp;
            ans+=temp;
        }
        cout<<ans<<endl;
    }

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

Problem F 天花乱坠

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

题意：

题解：计算几何+极限+等比数列求和

已知正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;
int t,n,m,k,p,l,r,u,v;
double 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(~scanf("%d",&n)){
        printf("%.2f\n",(100*n)/(1-cos(PI/n)));
    }

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

Problem G 说能过那是假的

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

题意：

题解：

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;
ll ans,cnt,flag,temp,sum,cot;
char ch[100007];
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("%s",ch);
    int len=strlen(ch);
    for(int i=0;i<len;i++)
        if(ch[i]=='Z')cnt++;
    for(int i=0;i<len;i++){
        if(ch[i]=='O')cot++;
        if(ch[i]=='R')ans+=cot*cnt;
        if(ch[i]=='Z')cnt--;
    }
    printf("%lld\n",ans);
    //}

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

Problem H 蛇皮走位

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

题意：

题解：

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=1000+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;
char a[N][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(~scanf("%d",&n)){
        int pos=0;
        for(int i=1;i<=2*n+1;i++){
            if(i&1)
                for(int j=1;j<=2*n+1;j++){
                    a[i][j]=pos+'a';
                    pos++;
                    pos%=26;
                }
            else
                for(int j=2*n+1;j>=1;j--){
                    a[i][j]=pos+'a';
                    pos++;
                    pos%=26;
                }
        }
        for(int i=1;i<=2*n+1;i++){
            for(int j=1;j<=2*n+1;j++)
                printf("%c",a[i][j]);
            cout<<endl;
        }
    }

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

Problem I 滑稽树上滑稽果

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

题意：求

题解：组合数学+预处理+逆元+莫队算法+分块

设

易得：

C++版本一

Problem J 

题意：

题解：

C++版本一

Problem K 

题意：

题解：

C++版本一