layout: post
title: 2018 German Collegiate Programming Contest (GCPC 18)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
C.Coolest Ski Route (记忆化搜索)
题意
给出一个有向图,求出一个权值最长的链,
题解
暴力dfs会超时,所以直接储存每个起点能走到的最远距离
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m;
struct node{
int v,c;
};
vector<node>G[maxn];
int dp[maxn];
int dfs(int now){
if(dp[now]!=-1)return dp[now];
int ans=0;
for(auto i:G[now]){
ans=max(ans,dfs(i.v)+i.c);
}
return dp[now]=ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n>>m;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
G[x].push_back(node{y,z});
}
int mx=-inf;
for(int i=1;i<=n;i++){
if(dp[i]==-1){
mx=max(mx,dfs(i));
}
}
cout<<mx<<endl;
return 0;
}
D.Down the Pyramid (不等式)
题意
金字塔的每一层都比上一层多一个，并且上一层的值是下一层的两个相邻之和
给出第n层，让你求出第N+1层的值有多少种可能性（需要保证每一个数都大于等于0）
题解
比赛一直想不出，付队做的.想法是，
假设给出的值是a1,a2,a3,a4,
假设第一个位置（b1）是X,那么第二个位置(b2)的值就是a1-x,第三个位置的值就是a2-(a1-x);
可以发现都和第一个假设的位置的值x有关,所以我们只要保证这个过程每个位置的值都大于0就可以求出X的可能取值
a1-x>=0 a2-a1-x>=0 ->x<=a1 x<=a2-a1;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=0;
int mi=0,mx=a[1];
for(int i=1;i<=n;i++){
ans=a[i]-ans;
if(i&1)mx=min(mx,ans);
else mi=max(mi,-ans);
}
if(mx<mi)cout<<0<<endl;
else cout<<mx-mi+1<<endl;
return 0;
}
Expired License (线性筛)
题意
给定你两个最多带5位小数的double型a,b，让你用用一对素数x y表示他们的比值。
题解
先把double变成整数型;注意四舍五入;然后求一下gcd 判断化简后是否都是素数即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-7;
bool check[maxn];
int phi[maxn];
int prime[maxn];
int tot;
void phi_and_prime_table(int N){
memset(check,false,sizeof(check));
phi[1]=1;
tot=0;
for(int i=2;i<=N;i++){
if(!check[i]){
prime[tot++]=i;
phi[i]=i-1;
}
for(int j=0;j<tot;j++){
if(i*prime[j]>N)break;
check[i*prime[j]]=true;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else{
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m;
int t;
phi_and_prime_table(10000000+10);
check[1]=true;
cin>>t;
while(t--){
double a,b;
cin>>a>>b;
int C=(int)((a+eps)*100000),D=(int)((b+eps)*100000);
int gc=__gcd(C,D);
C/=gc;D/=gc;
if(!check[C]&&!check[D])cout<<C<<" "<<D<<endl;
else if(C==1&&D==1)cout<<"2 2"<<endl;
else
cout<<"impossible"<<endl;
}
return 0;
}
F.Fighting Monsters (打表找规律)
题意
给出N个怪兽，问是否选择两个怪兽根据题意战斗之后 活下来的那个怪剩下一滴血
题解
根据题意打表后发现选择的两个怪兽血量必须符合斐波那契数列的相邻两项值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int m[maxn];
bool isok(int a,int b){
int aa=a,bb=b;
int i=1;
while(aa>0&&bb>0){
if(i&1)aa-=bb;
else bb-=aa;
i++;
}
if(aa==1||bb==1)cout<<"a="<<a<<" b="<<b<<endl;
aa=a,bb=b;
i=1;
while(aa>0&&bb>0){
if(i&1)bb-=aa;
else aa-=bb;
i++;
}
if(aa==1||bb==1)cout<<"a="<<a<<" b="<<b<<endl;
}
int F[maxn];
int num[maxn];
int id[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
/* for(int i=1;i<=1000;i++){
for(int j=i;j<=1000;j++){
isok(i,j);
}
}*/
F[1]=F[2]=1;
for(int i=3;i<=31;i++){
F[i]=F[i-1]+F[i-2];
// cout<<F[i]<<endl;
}
int n;
cin>>n;
int flag=0,one;
for(int i=1;i<=n;i++){
cin>>m[i];
if(!flag&&m[i]==1)flag=1,one=i;
num[m[i]]++;
id[m[i]]=i;
}
int f=0;
if(num[1]>=2){
cout<<one<<" "<<id[1]<<endl;
return 0;
}
for(int i=2;i<=30;i++){
if(num[F[i]]&&num[F[i+1]]){
f=1;
cout<<id[F[i]]<<" "<<id[F[i+1]]<<endl;
break;
}
}
if(!f)cout<<"impossible"<<endl;
return 0;
}
H.Hyper Illuminati
题意
给定一个数N(<1e16)，问是否存在n和s，满足1n+2n+3n+...sn=N；输出n+1，s
题解
slove by 付队，
如果2<=n<=53，我们发现s不会太大，我们可以把所有的都求出来；如果n>53，则有s<=2，我们可以把s=2的值都求出来。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll ans=0,n;
cin>>n;
for(int i=2;i<=53;i++){
ans=0;
for(ll j=1;j<=n;j++){
ll tmp=1;
for(ll k=1;k<=i;k++){
if(tmp>n/j){tmp=n+1;break;}
tmp*=j;
}
if(tmp>n)break;
ans+=tmp;
if(ans==n)return cout<<i+1<<" "<<j<<endl,0;
if(ans>n)break;
}
}
ll tmp=1;
for(ll j=1;j<=n;j++){
tmp*=2LL;
if(j>=2){
if(tmp+1==n)return cout<<j+1<<" "<<2<<endl,0;
}
if(tmp+1>=n)break;
}
cout<<"impossible"<<endl;
return 0;
}
I.It's Time for a Montage (枚举暴力)
题意
就是两边按顺序打架，如果当前相等就比下一个 直到比出胜负，但是主角可以选择每回合所有怪增加1点攻击，如果最后没怪并且主角攻击大于等于另一个就赢 ，问主角最少需要等多少回合;
题意
因为攻击力最大值只有1000 所以直接枚举暴力就行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int h[maxn];
int v[maxn];
int isok(int x,int n){
for(int i=1;i<=n;i++){
if(h[i]-v[i]+x==0)continue;
else if(h[i]-v[i]+x>0)return true;
else return false;
}
return true;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>h[i];
for(int i=1;i<=n;i++)cin>>v[i];
int ans=0;
for(int i=0;i<=1000;i++){
if(isok(i,n)){
cout<<i<<endl;
return 0;
}
}
return 0;
}
Logic Puzzle
题意
：给你一个大格子，然后在中心格子填黑点，每个格子中有显示以它为中心的3*3格子有多少个黑点，让你构造中心格子的黑点， （就是扫雷
题解
从左上开始枚举对应的雷都是固定的，所以直接扫过去判断是否可以扫完就行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int dx[9]={0,0,0,1,-1,1,1,-1,-1};
int dy[9]={0,1,-1,0,0,1,-1,1,-1};
int a[150][150],vis[150][150];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)cin>>a[i][j];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(a[i][j]==1){
vis[i+1][j+1]=1;
for(int k=0;k<=8;k++){
if(i+1+dx[k]>=0&&i+1+dx[k]<=n+1&&j+1+dy[k]>=0&&j+1+dy[k]<=m+1)
a[i+1+dx[k]][j+1+dy[k]]--;
}
}
}
}
for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++){
if(a[i][j]){
cout<<"impossible"<<endl;return 0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j])cout<<"X";
else cout<<".";
}
cout<<endl;
}
return 0;
}