吉首大学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++版本一

 

全部评论

相关推荐

11-20 15:36
北京外国语大学 产品经理
点赞 评论 收藏
分享
今天 10:23
中山大学 算法工程师
结束了，一切都结束了。。
终于终于终于结束了，这难熬又最难忘的秋招。感觉甚至比高考难得多，因为它没有固定标准，没有固定时间，没有固定节奏，只有无尽的努力和等待。我是大模型算法方向，感觉这个岗位今年更卷，虽然貌似每个公司招的岗位多，但是平分到每个岗位就没几个hc了，尤其今年要求还格外高，就格外难。&nbsp;现在终于都结束了，拿下了4个大厂，不敢回顾秋招，就记录一下我的offer吧，给秋招画上一个句号。&nbsp;我的4个offer：美团：base上海，客服大模型，不太核心京东：base北京，京东零售，做导购大模型腾讯：base深圳，实习转正，组内氛围好，做老牌产品的，主要做算法策略百度：base北京，大模型算法岗，小度业务线&nbsp;我是最先拿到...
超脱的劳伦斯是我：秋招参加完，做什么事情都会成功的
投递美团等公司10个岗位 >
点赞 评论 收藏
分享
11-18 09:44
Java
是项目太简单了吗，投了半个月日常实习，啥也没有😭我是需要去再整个微服务项目吗
小白也想要offer：简历别放洋屁，搞不还还放错了，当然你投外企除外，以上纯属个人观点
点赞 评论 收藏
分享
11-22 00:39
安徽大学 Java
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
322333次浏览 2990人参与
# 上班苦还是上学苦呢？ #
69713次浏览 615人参与
# 百度开奖 #
179799次浏览 1126人参与
# 地方国企笔面经互助 #
4397次浏览 12人参与
# 如果有时光机，你最想去到哪个年纪？ #
20573次浏览 349人参与
# 选完offer后，你后悔学本专业吗 #
21498次浏览 155人参与
# 阿里云管培生offer #
36303次浏览 420人参与
# 如何一边实习一边秋招 #
995783次浏览 12661人参与
# 我的实习求职记录 #
6067157次浏览 83521人参与
# 招聘要求与实际实习内容不符怎么办 #
10674次浏览 276人参与
# 入职第一天，你准备什么时候下班 #
21485次浏览 144人参与
# 许愿池 #
214521次浏览 2534人参与
# bilibili求职进展汇总 #
32864次浏览 354人参与
# 学历or实习经历，哪个更重要 #
53458次浏览 417人参与
# 实习工作，你找得还顺利吗？ #
247535次浏览 2902人参与
# 海康威视求职进展汇总 #
400319次浏览 3407人参与
# 通信硬件薪资爆料 #
607311次浏览 5150人参与
# 正在实习的你，几点下班 #
52974次浏览 395人参与
# 如果再来一次，你还会学硬件吗 #
95063次浏览 1169人参与
# 工作两年想退休了 #
52949次浏览 672人参与
# 软件开发薪资爆料 #
2191890次浏览 21874人参与
# 我的失利项目复盘 #
668104次浏览 11247人参与
牛客网
牛客企业服务