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++版本一