test20190526

Posted on | Views:

感觉 $T3$ 很假.

$tweak$

  • 题面有误.题意是每次可以选一条边,权值修改为任意非负整数,问至少改多少条可以使 $1\to n$ 的最短路 $\leq c$ .
  • 显然可以贪心,每次修改时都改成 $0$ .设 $f(i,j)$ 表示 $1\to i$ ,改了 $j$ 条边时的最短路.用 $spfa$ 转移即可. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{if(ch=='-') k=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')
		{x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return k*x;
}
const int MAXN=1e3+10;
int ecnt=0,head[MAXN],to[MAXN],nx[MAXN],val[MAXN];
inline void addedge(int u,int v,int w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	val[ecnt]=w;
	head[u]=ecnt;
}
int n,m,c;
int f[MAXN][MAXN],tot=0;
int vis[MAXN];
queue<int> q;
void spfa()
{
	memset(f,63,sizeof f);
	int inf=f[0][0];
	f[1][0]=0;
	vis[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			bool flag=false;
			for(int j=0;j<=m;++j)
			{
				if(f[u][j]>=inf)
					break;
				if(f[u][j]<=f[v][j+1])
				{
					f[v][j+1]=f[u][j];
				}
				if(f[u][j]+val[i]<=f[v][j])
				{
					f[v][j]=f[u][j]+val[i];
					if(!j)
						flag=true;
				}
			}
			if(flag && !vis[v])
			{
				vis[v]=1;
				q.push(v);
			}
		}
	}
}
int main()
{
	freopen("tweak.in","r",stdin);
	freopen("tweak.out","w",stdout);
	n=read(),m=read(),c=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		addedge(u,v,w);
	}
	spfa();
	for(int i=0;i<=m;++i)
		if(f[n][i]<=c)
		{
			cout<<i<<endl;
			return 0;
		}
	return 0;
}

$coins$

  • 把每个硬币看做多项式 $(x^{a_i}+1)$ ,如果每个硬币都可以用,方案数就是 $\prod (x^{a_i}+1)$ 这个多项式中系数非零的 $x^k(k>0)$ 的个数.
  • 限定某个硬币 $i$ 不能用,只需要在多项式 $\prod (x^{a_i}+1)$ 中把 $(x^{a_i}+1)$ 除去,然后统计答案.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{if(ch=='-') k=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')
		{x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return k*x;
}
int n,a[101];
const int MAXN=3e5+10;
ll poly[MAXN],tmp[MAXN];
ll stk[MAXN],sk[MAXN];
int deg=0,tp=0;
int query(int p)
{
	tp=0;
	int Deg=deg,res=0;
	while(Deg)
	{
		ll s=poly[Deg];
		if(!s)
		{
			--Deg;
			continue;
		}
		if(!tmp[Deg-p] && Deg-p)
			++res;
		tmp[Deg-p]+=s;
		stk[++tp]=Deg-p;
		poly[Deg-p]-=s;
		sk[tp]=s;
		--Deg;
	}
	for(int i=1;i<=tp;++i)
	{
		tmp[stk[i]]=0;
		poly[stk[i]]+=sk[i];
	}
	return res;
}
int main()
{
	freopen("coin.in","r",stdin);
	freopen("coin.out","w",stdout);
	n=read();
	poly[0]=1;
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		for(int j=deg;j>=0;--j)
			poly[a[i]+j]+=poly[j];
		deg+=a[i];	
	}
	for(int i=1;i<=n;++i)
		printf("%d\n",query(a[i]));
	return 0;
}

$cakes$

  • $std:$ 维护一个堆,存储每种大小的元素数目.每次取出顶部三个,做最多的三元组,把剩余的放回去.

并不知道我的贪心哪里出了问题.