Problem C 六学家的困惑
https://ac.nowcoder.com/acm/contest/625/C
题解：区间DP
1、对给定的两个字符串按规则以后最大排列（区间DP）
2、反转字符串1，与字符串2拼接，得到字符串3
3、初始化DP数组仅字符串1和字符串2的衔接的两个字符
4、区间DP
/*
*@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];
string str1,str2,str3;
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);
int T=0;
while(t--){
string dp[3][100][100];
//scanf("%d",&n);
cin>>str1>>str2;
int len1=str1.size();
int len2=str2.size();
for(int i=0;i<len1;i++){
dp[0][i][i]=str1[i];
}
for(int i=0;i<len2;i++){
dp[1][i][i]=str2[i];
}
for(int i=2;i<=len1;i++){
for(int j=0;j+i-1<len1;j++){
int l=j;
int r=j+i-1;//cout<<dp[0][l+1][r]+str1[l]<<endl;
if(str1[r]+dp[0][l][r-1]<str1[l]+dp[0][l+1][r]){
dp[0][l][r]=str1[l]+dp[0][l+1][r];
}else{
dp[0][l][r]=str1[r]+dp[0][l][r-1];
}//cout<<dp[0][l][r]<<endl;
}
}
for(int i=2;i<=len2;i++){
for(int j=0;j+i-1<len2;j++){
int l=j;
int r=j+i-1;
if(str2[r]+dp[1][l][r-1]<str2[l]+dp[1][l+1][r]){
dp[1][l][r]=str2[l]+dp[1][l+1][r];
}else{
dp[1][l][r]=str2[r]+dp[1][l][r-1];
}
}
}
for(int i=0;i<len1+len2;i++){
dp[2][i][i]="";
}
reverse(&dp[0][0][len1-1][0],&dp[0][0][len1-1][len1]);
// cout<<dp[0][0][len1-1]<<endl;
// cout<<dp[1][0][len2-1]<<endl;
str3=dp[0][0][len1-1]+dp[1][0][len2-1];
dp[2][len1-1][len1-1]=dp[0][0][len1-1][len1-1];
dp[2][len1][len1]=dp[1][0][len2-1][0];
// cout<<str3<<endl;
// cout<<dp[2][len1-1][len1-1]<<" "<<dp[2][len1][len1]<<endl;
for(int i=2;i<=len1+len2;i++){
for(int j=0;j+i-1<len1+len2;j++){
int l=j;
int r=j+i-1;
if(dp[2][l+1][r]!=""&&dp[2][l][r-1]!=""){
if(dp[2][l][r-1]+str3[r]<dp[2][l+1][r]+str3[l]){
dp[2][l][r]=dp[2][l+1][r]+str3[l];
}else{
dp[2][l][r]=dp[2][l][r-1]+str3[r];
}
}else if(dp[2][l+1][r]!=""||dp[2][l][r-1]!=""){
if(dp[2][l+1][r]!="")
dp[2][l][r]=dp[2][l+1][r]+str3[l];
else
dp[2][l][r]=dp[2][l][r-1]+str3[r];
}
//cout<<dp[2][l][r]<<endl;
}
}
printf("Case #%d: ",++T);
cout<<dp[2][0][len1+len2-1]<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem E 数独挑战
https://ac.nowcoder.com/acm/contest/625/E
题解：数独游戏裸题
/*
*@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
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=10000;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,q;
ll ans=-1;
struct node {
int lx , sum ;
}line[ 11 ] ;//记录每行需要填的零的个数;
int a[10][10];
int b[10][10];
bool row[10][10];
bool col[10][10];
bool block[10][10];
void dfs(int id,int x,int y){
if(id==9&&y==9){
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
cout << a[i][j]<< " ";
}
cout << endl;
}
return;
}
if(y==9){
y=1;
x=line[++id].lx;
}else{
y++;
}
if(!a[x][y]){
for(int i=1;i<=9;i++){
if(!row[x][i]&&!col[y][i]&&!block[b[x][y]][i]){
row[x][i]=1;
col[y][i]=1;
block[b[x][y]][i]=1;
a[x][y]=i;
dfs(id,x,y);
a[x][y]=0;
row[x][i]=0;
col[y][i]=0;
block[b[x][y]][i]=0;
}
}
}else{
dfs(id,x,y);
}
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//scanf("%d",&n);
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
t=(i-1)*3+j;
int r=(i-1)*3;
int c=(j-1)*3;
for(int k=1;k<=3;k++){
for(int l=1;l<=3;l++){
b[r+k][c+l]=t;
}
}
}
}
for(int i=1;i<=9;i++){
line[i].lx=i;
line[i].sum=0;
for(int j=1;j<=9;j++){
scanf("%d",&a[i][j]);
if(a[i][j]){
line[i].sum++;
row[i][a[i][j]]=1;
col[j][a[i][j]]=1;
block[b[i][j]][a[i][j]]=1;
}
}
}
dfs(1,line[1].lx,0);
//cout << "Hello world!" << endl;
return 0;
}
Problem F 翻牌游戏
https://ac.nowcoder.com/acm/contest/625/F
题解：规律
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("%.2f\n",(double)2*n-1);
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 5005;
double arr[MAXN][MAXN];
int t, n;
void Init(){
arr[1][1] = 1.0;
arr[2][2] = 1.0 / 3.0;
arr[2][3] = arr[2][2];
arr[2][4] = arr[2][3];
for(int i = 3; i <= 5000; i ++){
for(int j = i; j <= 2 * i; j ++){
if(j == 2 * i){
double ans = 1.0;
for(int z = i; z < 2 * i; z ++){
ans -= arr[i][z];
}
arr[i][j] = ans;
}
else if(j == i){
double ans = (2.0 * i) / (2.0 * i * (2.0 * i - 1.0));///1/5
arr[i][j] = arr[i - 1][i - 1] * ans;
}
else{
double ans = (2.0 * i) / (2.0 * i * (2.0 * i - 1.0));
arr[i][j] = ans * arr[i - 1][j - 1] * i;
}
}
}
}
int main()
{
scanf("%d", &t);
Init();
while(t --){
scanf("%d", &n);
double re = 0.0;
for(int i = n; i <= 2 * n; i ++){
re += (arr[n][i] * i * 1.0);
}
printf("%.0f.00\n", re);
}
return 0;
} Problem H Parco_Love_GCD
https://ac.nowcoder.com/acm/contest/625/H
C++版本一
题解：递推
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define FI first
#define SE second
#define PB push_back
typedef pair<LL,LL> PII;
const int N=1e6+7,INF=1e9,mod=1e9+7;
int n,m;
LL a[N];
vector<PII>v[N];
int main()
{
cin>>n;
LL ans=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
ans=(ans+a[i])%mod;
if(i==1){
v[i].PB(make_pair(a[i],1));continue;
}
v[i].PB(make_pair(a[i],i));
/*
if(a[i]!=v[i-1][0].FI){
v[i].PB(make_pair(a[i],i));
}
*/
int l=v[i-1].size();
LL st=i;
for(int j=0;j<l;j++){
LL k=__gcd(v[i-1][j].FI,a[i]);
if(k==1){
ans=(ans+st-1)%mod;
v[i].PB(make_pair(1,1));
break;
}
ans=(ans+k*(st-v[i-1][j].SE))%mod;
st=v[i-1][j].SE;
if(k==v[i][v[i].size()-1].FI){
v[i][v[i].size()-1].SE=v[i-1][j].SE;
}
else v[i].PB(make_pair(k,v[i-1][j].SE));
}
//if(a[i]%v[i-1][0].FI==0)continue;
}
cout<<ans<<endl;
return 0;
} 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=500000+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];
char str;
struct node{
int val,id;
node(){};
node(int _val,int _id):val(_val),id(_id){}
};
vector<node>v[N];
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]);
v[i].push_back({a[i],i});
ans=(ans+a[i])%MOD;
if(i==1)
continue;
int len=v[i-1].size();
int pos=i;
for(int j=0;j<len;j++){
int k=__gcd(v[i-1][j].val,a[i]);
if(k==1){
ans=(ans+pos-1)%MOD;
v[i].push_back({1,1});
break;
}
ans=(ans+(ll)k*(pos-v[i-1][j].id))%MOD;
pos=v[i-1][j].id;
if(k==v[i][v[i].size()-1].val){
v[i][v[i].size()-1].id=v[i-1][j].id;
}
else v[i].push_back({k,v[i-1][j].id});
}
}
cout<<ans<<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/625/I
题解：按低买高卖的原则
/*
*@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=500000+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);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int pos=1;
int maxl=a[1];
for(int i=2;i<=n;i++){
if(a[i]<maxl){
ans+=maxl-a[pos];
pos=i;
}
maxl=a[i];
}
ans+=maxl-a[pos];
cout<<ans<<endl;
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Problem L 石头剪刀布
https://ac.nowcoder.com/acm/contest/625/L
题解：
/*
*@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;
if(str[0]=='S'){
cout<<"Rock"<<endl;
}else if(str[0]=='R'){
cout<<"Paper"<<endl;
}else{
cout<<"Scissors"<<endl;
}
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
京公网安备 11010502036488号