2019.01.22【NOIP普及组】模拟赛C组 总结&解题报告

$Introduction$Introduction

XC说今天让我们休息放松，AB组没有比赛，去C组划水，祝斐大爷双双AK愉快AK

---

题解

T1 小明解密码

$Describe$Describe

求$x^y\ mod\ 10$xy mod 10的值

---

$Solution$Solution

什么垃圾水题，说到水，我就想起东海，说到东海，我就想起东海龙宫，一说到东海龙宫，就不得不题今年下半年中美合拍的西游记，我将继续扮演美猴王这一艺术角色，文体两开花，希望大家多多关注。

---

$Code$Code

#include<cstdio>
#define whf 10//记得要%whf
#define file(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;long long n,m;int t;
long long ksm(long long x,long long y)
{
	x%=whf;
	long long ans=1;
	for(;y;y>>=1,(x*=x)%=whf) if(y&1) (ans*=x)%=whf;
	return ans;
}
signed main()
{
	file(a);
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&m);
		printf("%lld\n",ksm(n,m));
	}
}

---

T2 小明在边塞

$Describe$Describe

数字金字塔了解一下

---

$Solution$Solution

又是什么水题，说到水……滚！你怎么章口就来

---

$Code$Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define file(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;int a[501][501],f[501][501],n,m;
signed main()
{
	file(b);
	memset(f,0xcf,sizeof(f));
	f[1][0]=0;f[0][1]=0;
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)
	 for(register int j=1;j<=m;j++)
	{
		scanf("%d",&a[i][j]);
		if(a[i][j]==1) a[i][j]=-1;
		if(a[i][j]==2) a[i][j]=1;
		f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
	}
	printf("%d",f[n][m]);
}

T3 小明逛超市

$Describe$Describe

背包问题了解一下

---

$Solution$Solution

什么鬼水题

---

$Code$Code

#include<cstdio>
#include<algorithm>
#define file(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;long long f[10001],p,m,n,w;
bool ok;
signed main()
{
	file(c);
	scanf("%lld%lld",&m,&n);
	for(register int i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&w,&p,&ok);
		if(ok) for(register int j=m;j>=w;j--) f[j]=max(f[j-w]+p,f[j]);
		else for(register int j=w;j<=m;j++)f[j]=max(f[j-w]+p,f[j]);
	}
	printf("%lld",f[m]);
}

---

T4 小明游天界

$Describe$Describe

一张有向无环图，要求从1点走到$n$n点价值总和正好等于$m$m的最大经过点数

---

$Solution$Solution

分层图$dp$dp，设$f[i][j]$f[i][j]表示终点为第$j$j个点，价值总和为$i$i的方案数，得到

$f[y][i+w]=max(f[y][i+w],f[j][i]+1)$f[y][i+w]=max(f[y][i+w],f[j][i]+1)

$y$y为$j$j的子节点
时间复杂度$O(mv)\approx 1e8$O(mv)≈1e8，常数很大，要开氧气

---

$Code$Code

#pragma GCC optimize(2)
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define file(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
using namespace std;int tot=0,n,m,v,x,y,z,ans,l[1001],f[1001][1001];
struct node{int next,to,w;}e[100001];
inline void add(register int u,register int v,register int w){e[++tot]=(node){l[u],v,w};l[u]=tot;return;}
inline long long read()
{
	char c;int d=1;long long f=0;
	while(c=getchar(),!isdigit(c))if(c=='-')d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
inline void write(long long x){if(x>9)write(x/10);putchar(x%10+48);return;}
void work()
{
	f[1][0]=1;
	for(register int i=0;i<=m;i++)
	 for(register int j=1;j<=n;j++)	
	{
		if(f[j][i]<=0) continue;//小优化
	  	for(register int k=l[j];k;k=e[k].next)
	  	{
	  		int y=e[k].to,w=e[k].w;
	  		if(i+w>m) continue;//小优化
	  		f[y][i+w]=max(f[y][i+w],f[j][i]+1);
		}
	}
	return;
}
signed main()
{
	file(d);
	memset(f,0xcf,sizeof(f));
	n=read();m=read();v=read();
	for(register int i=1;i<=v;i++) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
	work();
	if(f[n][m]<=0) return puts("-1")&0;
	write(f[n][m]);
}

---

$All\ in\ all$All in all

这次的比赛总体难度比较低，只有第四题有挑战性，差点没做出来。以后要多积累做题经验，做的题多了自然就会了

---

后续

中午狼人杀愉快至极！