# Noip2017普及组题解

Posted by yjjr's blog on February 6, 2018 1 minutes to read

# T1

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

int main()
{
int a,b,c;
cin>>a>>b>>c;
cout<<a*0.2+b*0.3+c*0.5<<endl;
return 0;
}


# T2

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
int n,q,len,ans,a[1000006],s;
int main()
{
cin>>n>>q;
rep(i,1,n)cin>>a[i];
sort(a+1,a+1+n);
while(q--){
ans=-1;
cin>>len>>s;
int t=1;
while(len--)t*=10;
rep(i,1,n)
if(a[i]%t==s){
ans=a[i];
break;
}
printf("%d\n",ans);
}
return 0;
}


# T3

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define inf 0x3f3f3f
using namespace std;
const int maxn=1006,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m,x,y,opt,Map[maxn][maxn],f[maxn][maxn];
void dfs(int x,int y,int p){
rep(i,0,3){
int nowx=x+dx[i],nowy=y+dy[i];
if(nowx>n||nowx<1||nowy>n||nowy<1)continue;
if(~Map[nowx][nowy]){
if((~Map[x][y]?Map[x][y]:p)==Map[nowx][nowy])
{
if(f[nowx][nowy]>f[x][y])f[nowx][nowy]=f[x][y],dfs(nowx,nowy,Map[nowx][nowy]);
}
else{
if(f[nowx][nowy]>f[x][y]+1)f[nowx][nowy]=f[x][y]+1,dfs(nowx,nowy,Map[nowx][nowy]);
}
}
else{
if(Map[x][y]==-1)continue;
else if(f[nowx][nowy]>=f[x][y]+2)f[nowx][nowy]=f[x][y]+2,dfs(nowx,nowy,Map[x][y]);
}
}
}
int main()
{
mem(Map,-1);
mem(f,inf);
cin>>n>>m;
rep(i,1,m){
cin>>x>>y>>opt;
Map[x][y]=opt;
}
f[1][1]=0;
dfs(1,1,0);
if(f[n][n]==1061109567)cout<<"-1\n";
else cout<<f[n][n]<<endl;
return 0;
}


# T4

f[i]表示跳前i个格子，且停在第i个格子最大分数；

sc[i]表示第i个格子的分数。

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const ll maxn=5e5+6,inf=1844387848000;
ll dis[maxn],sc[maxn],f[maxn],n,d,k,x,y;
bool check(int x)
{
deque<ll>que;
ll from=0,stepl=max(d-x,(ll)1),stepr=d+x;
rep(i,1,n){
while(dis[from]+stepl<=dis[i]){
while(!que.empty()&&f[que.back()]<=f[from])que.pop_back();
que.push_back(from++);
}
while(!que.empty()&&dis[que.front()]+stepr<dis[i])que.pop_front();
if(!que.empty())f[i]=f[que.front()]+sc[i];
else f[i]=-inf;
if(f[i]>=k) return 1;
}
return 0;
}
int main()
{
cin>>n>>d>>k;
ll sum=0;
rep(i,1,n){
cin>>x>>y;
dis[i]=x;sc[i]=y;
if(y>0)sum+=y;
}
if(sum<k){cout<<"-1\n";return 0;}
int l=1,r=dis[n],mid;
while(l<r){
mem(f,0);
mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<r<<endl;
return 0;
}