调整(tweak)
【问题描述】
已给定一个 N个点 M条边的有向图，点编号为1到N，第i条边为 （ui，vi）， 权值为 wi。
你可以进行一次操作，使得任意条边的权值变成非负整数。要求进行尽量少的操作次数，使
得点 1到点 N的最短路径长度变成 c。
题目保证， c小于在未进行任何操作之前的原图中 1到 N的最短路长度。
【输入文件】tweak.in
输入文件tweak.in 第一行三个整数，第一行三个整数，N，M和 c
接下来 M行，每一条边的信息 ui，vi和 wi，第 i行的表述第 i条边的信息。 保
证不会有自环存在，对于不同的 i和 j，（ui，vi）不同于 （uj，vj）。
【输出文件】tweak.out
输出文件 tweak.out 一行一个整数，要进行最少多少次操作才能使得最短路长度变为
c。
【输入样例】
3 3 3
1 2 3
2 3 3
1 3 8
【输出样例】
1
【样例说明】
将边 1，3的权值修改为 2就可以了。
【数据规模】
N<=100
M<=1000
0<=c<=100000
0<=wi<=10000
30%数据满足 M<=20
50%数据满足 M<=70
拆点最短路，才做过类似的题。
#include<bits/stdc++.h>
#define co const
template<class T>T read(){
T data=0,w=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
for(;isdigit(ch);ch=getchar())data=data*10+ch-'0';
return data*w;
}
template<class T>T read(T&x){
return x=read<T>();
}
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
co int N=101;
int n,m,c,dis[N*N],vis[N*N];
vector<pii> g[N*N];
priority_queue<pii> pq;
int main(){
freopen("tweak.in","r",stdin),freopen("tweak.out","w",stdout);
read(n),read(m),read(c);
for(int u,v,w;m--;){
read(u),read(v),read(w);
for(int i=0;i<n;++i) g[i*n+u].push_back(pii(i*n+v,w));
for(int i=0;i<n-1;++i) g[i*n+u].push_back(pii((i+1)*n+v,0));
}
memset(dis,0x3f,sizeof dis);
dis[1]=0,pq.push(pii(-dis[1],1));
for(int u;pq.size();){
u=pq.top().second,pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=0,v,w;i<g[u].size();++i){
v=g[u][i].first,w=g[u][i].second;
if(dis[v]>dis[u]+w) dis[v]=dis[u]+w,pq.push(pii(-dis[v],v));
}
}
for(int i=0;i<n;++i)if(dis[i*n+n]<=c){
printf("%d\n",i);break;
}
return 0;
}硬币(coin)
【问题描述】
你有n个硬币，第i个硬币面值为ai，现在总队长想知道如果丢掉了某个硬币，剩下的硬
币能组成多少种价值？（0 价值不算）
【输入】
第一行一个整数n
第二行 n 个整数：a1,a2…an。
【输出】
输出n行，第i行表示没有第i个硬币能组成多少种价值。
【输入输出样例】
coin.in
3
1 1 3
coin.out
3
3
2
【数据范围】
对于 30%的数据 1<=n<=50,1<=ai<=100；
对于 100%的数据 1<=n<=100,1<=ai<=3000。
01背包，bitset+卡常
#include<bits/stdc++.h>
#define co const
template<class T>T read(){
T data=0,w=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
for(;isdigit(ch);ch=getchar())data=data*10+ch-'0';
return data*w;
}
template<class T>T read(T&x){
return x=read<T>();
}
typedef long long ll;
using namespace std;
int n,a[101];
bitset<297001> pre,ans;
int main(){
freopen("coin.in","r",stdin),freopen("coin.out","w",stdout);
read(n);
for(int i=1;i<=n;++i) read(a[i]);
pre[0]=1;
for(int i=1;i<=n;++i){
ans=pre;
for(int j=i+1;j<=n;++j) ans|=ans<<a[j];
printf("%d\n",ans.count()-1);
pre|=pre<<a[i];
}
return 0;
}令 f[i]][j]为用前 i 个硬币组成 j 价值有都少种方案。
若我们已经知道了 f[n]，动规易得，如何直到少去某种硬
币之后的情况呢。我们可以把这种硬币当做我们最后才放进去
的，假设他的价值为 K.
那 么 f[n][0]..f[n][k-1]=f[n-1][0]..f[n-1][k-1] 。显然
f[n][j]=f[n-1][j-k]+f[n-1][j] ， 即
f[n-1][j]=f[n][j]-f[n-1][j-k]。根据这个转移和我们已得到
的信息，我们可以得到 f[n-1]。然后 f[n-1]中>0 的个数即答案。
f 数组可能暴数据范围，一种方法是高精，另一种方法是
hash,取摸等等。都可以实现
效率是 O(n^2*sum(ai))
不明所以
#include<cstdio>
#include<iostream>
using namespace std;
int N;
int A[101];
int f[3000010];
int w[3000010];
int main(){
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
scanf("%d",&N);
for (int i=1;i<=N;++i)
scanf("%d",&A[i]);
int MaxM=0;
f[0]=1;
for (int i=1;i<=N;++i){
for (int j=MaxM;j>=0;--j){
f[j+A[i]]+=f[j];
}
MaxM+=A[i];
}
int tot;
for (int i=1;i<=N;++i){
tot=0;
for (int j=0;j<A[i];++j){
w[j]=f[j];
if (w[j]) ++tot;
}
for (int j=A[i];j<=MaxM;++j){
w[j]=f[j]-w[j-A[i]];
if (w[j]) ++tot;
}
--tot;
printf("%d\n",tot);
}
fclose(stdin);
fclose(stdout);
}jklover写了一发多项式
#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)
【问题描述】
其实 moreD 是一个十分犀利的蛋糕师。他最喜欢的食物就是蛋糕。
一天，他自己做出了 N 个圆柱状的蛋糕，每个蛋糕都有一个底面圆的半径 Ri。高度都是一样的。
moreD 在开始享用他的蛋糕大餐之前忽然觉得，圆柱状的蛋糕没有什么诱惑力。moreD看到了别人结婚用的蛋糕都是很多很多层的，那样的蛋糕才比较给力。但是堆太多层的蛋糕比较困难，于是 moreD 想要堆出许多三层的蛋糕，再开始自己的蛋糕大餐。
当然，作为蛋糕师，moreD 在堆蛋糕的时候不会对蛋糕的形状有任何破坏，而且，moreD希望三层蛋糕的半径从上往下严格递增。这才是一个普通的好蛋糕。
但是 moreD 在考虑一个十分重要的问题，最多可以堆出多少三层蛋糕呢？
【输入格式】
输入第一行仅包含一个整数 N,表示蛋糕的数量。
接下来N个整数，表示每个蛋糕半径的大小Ri。
【输出格式】
输出一行仅包含一个整数，表示最多可以做成多少个蛋糕。
【输入输出样例一】
cakes.in
6
1 2 3 4 3 2
cakes.out
2
【输入输出样例二】
cakes.in
6
1 1 1 2 2 3
cakes.out
1
【数据范围】
对于 20%的数据 N<=10
对于 40%的数据 N<=2000
对于 60%的数据 N<=100,000
对于 100%的数据 N<=3,000,000 Ri<=N
考试的时候写了个伪算法。
实际上正解也非常sb，直接记录数字次数，每次贪心取出最大的三个统计答案。这样做一定是对的，因为不同次数之间一定可以组合出一种顺序。
#include <queue>
#include <cstdio>
#define MIN(a,b) (((a) < (b))?(a):(b))
using namespace std;
int top;
int bask[3000001],q[3000001];
inline unsigned int Get_uint()
{
char ch = getchar();
unsigned int j = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
j = j * 10 + ch - '0',
ch = getchar();
return j;
}
void push(int a)
{
q[++top] = a;
push_heap(q+1,q+top+1);
}
int pop()
{
pop_heap(q+1,q+top+1);
return q[top--];
}
int main()
{
freopen("cakes.in","r",stdin);
freopen("cakes.out","w",stdout);
int n,Ri;
scanf("%d",&n);
for(int i = 1;i <= n;++i)
{
//scanf("%d",&Ri);
Ri = Get_uint();
++bask[Ri];
}
top = 0;
for(int i = 1;i <= n;++i)
if (bask[i] > 0)
q[++top] = bask[i];
make_heap(q+1,q+top+1);
int u,v,w,ans = 0,mins;
while(top >= 3)
{
u = pop();
v = pop();
w = pop();
mins = MIN(MIN(u,v),w);
u -= mins,v -= mins,w -= mins,ans += mins;
if (u > 0) push(u);
if (v > 0) push(v);
if (w > 0) push(w);
}
printf("%d",ans);
fclose(stdin);fclose(stdout);
return 0;
}