NOIP 2014 提高组 合集
D1 T1 生活大爆炸版石头剪刀布
首先，先将两个人的猜拳序列都变得不小于n。然后逐个模拟。胜败什么的看表就行了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int ans1=0,ans2=0;
int a1[210],a2[210],s1[210],s2[210],k1,k2;
void calc(int x,int y)
{
if(x==0)
{
if(y==0) return;
else if(y==1) ans2++;
else if(y==2) ans1++;
else if(y==3) ans1++;
else ans2++;
}
else if(x==1)
{
if(y==0) ans1++;
else if(y==1) return;
else if(y==2) ans2++;
else if(y==3) ans1++;
else ans2++;
}
else if(x==2)
{
if(y==0) ans2++;
else if(y==1) ans1++;
else if(y==2) return;
else if(y==3) ans2++;
else ans1++;
}
else if(x==3)
{
if(y==0) ans2++;
else if(y==1) ans2++;
else if(y==2) ans1++;
else if(y==3) return;
else ans1++;
}
else
{
if(y==0) ans1++;
else if(y==1) ans1++;
else if(y==2) ans2++;
else if(y==3) ans2++;
else return;
}
}
int main()
{
int n,n1,n2; cin >> n >> n1 >> n2 ;
for(int i=1;i<=n1;i++) scanf("%d",&a1[i]);
for(int i=1;i<=n2;i++) scanf("%d",&a2[i]);
int cnt1=n/n1+(n%n1==0?0:1),cnt2=n/n2+(n%n2==0?0:1);
for(int i=1;i<=cnt1;i++) for(int j=1;j<=n1;j++) s1[++k1]=a1[j];
for(int i=1;i<=cnt2;i++) for(int j=1;j<=n2;j++) s2[++k2]=a2[j];
for(int i=1;i<=n;i++) calc(s1[i],s2[i]);
printf("%d %d
",ans1,ans2);
return 0;
}
D1 T2 联合权值
巨裸的树形dp，跟模拟没啥区别了。我开始看成了边不给定，然后管教练要prufer的ppt... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
#define mod 10007
using namespace std; typedef long long ll; ll maxn=0,ans=0;
ll w[N]; int to[N<<1],head[N],nxt[N<<1],tot;
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
ll rd() {ll x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
inline void add(int x,int y) {to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}
void dfs(int pos,int fa)
{
ll now1=w[fa],now2=0; ll sum=w[fa]%mod;
for(int i=head[pos];i;i=nxt[i]) if(to[i]!=fa)
{
// printf("%d")
if(w[to[i]]>=now1) now2=now1,now1=w[to[i]];
else if(w[to[i]]>=now2) now2=w[to[i]];
(ans+=sum%mod*w[to[i]]%mod)%=mod; (sum+=w[to[i]])%=mod;
dfs(to[i],pos);
}
maxn=max(maxn,now1*now2);
}
// void test()
// {
// puts("Fuck"); for(int i=1;i<=n;i++)
// }
int main()
{
int n=rd(); int x,y; for(int i=1;i<n;i++) x=rd(),y=rd(),add(x,y),add(y,x);
for(int i=1;i<=n;i++) w[i]=rd();
dfs(1,0); printf("%lld %lld
",maxn,ans*2%mod);
}
D1 T3 飞扬的小鸟
dp题。f[i][j]表示横坐标到i，高度到j的最少点击次数。
转移的话，上升我们考虑完全背包，下降用01背包即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10000+10;
const int M=2000+10;
int n,m,p;
int x[N],y[N];
int low[N],high[N];
int f[N][M];
bool e[N];
int main()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;++i)
{
low[i]=1;
high[i]=m;
}
int a,b,c;
for(int i=1;i<=p;++i)
{
scanf("%d%d%d",&a,&b,&c);
e[a]=1;
low[a]=b+1;
high[a]=c-1;
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=m;++i) f[0][i]=0;
for(int i=1;i<=n;++i)
{
for(int j=x[i]+1;j<=m+x[i];++j)
f[i][j]=min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1);
for(int j=m+1;j<=m+x[i];++j)
f[i][m]=min(f[i][m],f[i][j]);
for(int j=1;j<=m-y[i];++j)
f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
for(int j=1;j<low[i];++j)
f[i][j]=f[0][0];
for(int j=high[i]+1;j<=m;++j)
f[i][j]=f[0][0];
}
int ans=f[0][0];
for(int j=1;j<=m;++j)
{
ans=min(ans,f[n][j]);
}
if(ans<f[0][0]) printf("1
%d
",ans);
else
{
int i,j;
for(i=n;i>=1;i--)
{
for(j=1;j<=m;++j)
{
if(f[i][j]<f[0][0]) break;
}
if(j<=m) break;
}
ans=0;
for(int j=1;j<=i;++j) if(e[j]) ans++;
printf("0
%d
",ans);
}
return 0;
}
D2 T1 无线网络发射器选址
挨着枚举一遍就行...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 150
using namespace std;
int val[N][N]; int ans,tmp;
int main()
{
int d,n; cin >> d >> n ; int x,y,a;
for(int i=1;i<=n;i++) scanf("%d%d%d",&x,&y,&a),val[x][y]+=a;
for(int i=0;i<=128;i++) for(int j=0;j<=128;j++)
{
int x1,y1,x2,y2;
x1=max(0,i-d); x2=min(i+d,128);
y1=max(0,j-d); y2=min(j+d,128);
int now=0; for(int k=x1;k<=x2;k++) for(int l=y1;l<=y2;l++) now+=val[k][l];
if(ans<now) ans=now,tmp=1;
else if(ans==now) tmp++;
}
printf("%d %d
",tmp,ans);
}
D2 T2 寻找道路
先连反向边，从终点先dfs一遍，把所有能到终点的点打上标记。然后对于所有到不了终点的点，枚举所有出边，枚举到的都是不能在路径上出现的点，紧接着连正向边，从原点跑dij即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 10010
#define M 200010
#define mp make_pair
using namespace std; queue<int>q; priority_queue<pair<int,int> >que;
struct Node{int x,y;}a[M]; int head[N],nxt[M<<1],to[M<<1],tot;
int f[N]; bool vis[N],in[N]; int n,m,s,t;
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
inline void add(int x,int y) {to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}
void dfs(int pos,int fa)
{
if(vis[pos]) return;
vis[pos]=true; for(int i=head[pos];i;i=nxt[i]) if(to[i]!=fa) dfs(to[i],pos);
}
void bfs()
{
for(int i=1;i<=n;i++) if(!vis[i]) in[i]=true;
while(!q.empty())
{
puts("Fuck");
int x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
{
if(in[to[i]]) continue;
in[to[i]]=true;
q.push(to[i]);
}
}
}
void dij(int s)
{
memset(f,0x3f,sizeof f); memset(vis,false,sizeof vis);
f[s]=0; que.push(mp(0,s)); vis[s]=1;
while(!que.empty())
{
while(-que.top().first>f[que.top().second]&&!que.empty()) que.pop();
if(que.empty()) return;
int x=que.top().second;
que.pop(); for(int i=head[x];i;i=nxt[i])
{
// printf("%d %d
",que.top().first,que.top().second);
if(f[to[i]]>f[x]+1&&!vis[to[i]])
{
vis[to[i]]=true;
f[to[i]]=f[x]+1,que.push(mp(-f[to[i]],to[i]));
}
}
}
}
void test()
{
for(int i=1;i<=n;i++) printf("%d ",in[i]?1:0); puts("");
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=m;i++) a[i].x=rd(),a[i].y=rd(),add(a[i].y,a[i].x);
s=rd(),t=rd(); dfs(t,t);
for(int i=1;i<=n;i++) if(!vis[i])
{
in[i]=true;
for(int j=head[i];j;j=nxt[j])
{
in[to[j]]=true;
}
}
// test();
memset(head,0,sizeof head); tot=0;
for(int i=1;i<=m;i++)
{
if(in[a[i].x]||in[a[i].y]) continue;
add(a[i].x,a[i].y);
// printf("%d %d
",a[i].x,a[i].y);
}
dij(s);
if(f[t]==0x3f3f3f3f) puts("-1");
else printf("%d
",f[t]);
return 0;
}
D2 T3 解方程
我去...这题，看了题解才明白出题人的意图... ...
我做题的时候还在那里骂：卧槽，傻逼出题人又tm出高精度
然后是个rp题...
998244353可过。
但是为了尊敬长者，我们用19260817
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define mod 19260817
using namespace std;
typedef long long ll;
bool t=true;
int n,m,ans,cnt,sum=0;
int A[103],key[1000003];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
ll rd()
{
ll x=0; char c=nc(); int f=1; if(c=='-') f=-1;
while(!isdigit(c))
{
c=nc();
if(c=='-') f=-1;
}
while(isdigit(c)) (x=(x<<3)%mod+(x<<1)%mod+(c^48)%mod)%=mod,c=nc();
return x*f;
}
bool calc(ll x)
{
sum=0;
for(ll i=n;i>=1;i--)
{
sum=((A[i]+sum)*x)%mod;
}
sum=(sum+A[0])%mod;
return !sum;
}
int main()
{
n=rd();
m=rd();
for(ll i=0;i<=n;i++) A[i]=rd();
for(ll i=1;i<=m;i++)
{
if(calc(i))
{
t=false;
ans++;
key[++cnt]=i;
}
}
printf("%d
",ans);
for(ll i=1;i<=cnt;i++) printf("%d
",key[i]);
return 0;
}