T1 0 pts
T2 10pts
T3 0 pts
好文推荐
图论中的二分
关于一个图中是否存在负环
1383: 小奇挖矿
___可以发现，当前的决策只对后面的开采有影响，且剩余耐久度与之后的开采收益成正比.
___如果倒着考虑这个问题，得出i-n的星球"1"耐久度所能获得的最大收益，从后往前dp，得出最大值最后乘w就是答案
考试技巧：zz的我懒得打暴力，结果dp写挂了……下次还是打包里吧，毕竟
** 绵阳市第三医院委提醒您:骗分千万条,暴力第一条,代码不规范,欧阳两行泪 **
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dwn(i,a,b) for(int i=a;i>=b;i--)
#define N 100001
using namespace std;
double k,c,ans;
int n,w;
int op[N],a[N];
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d%lf%lf%d",&n,&k,&c,&w);
rep(i,1,n)
scanf("%d%d",&op[i],&a[i]);
k=1-0.01*k,c=1+0.01*c;
dwn(i,n,1)
{
if(op[i]==1)
ans=max(ans,ans*k+a[i]);
else
ans=max(ans,ans*c-a[i]);
}
printf("%.2f",ans*w);
return 0;
}1384: 小奇的数列
90pts 做法（前缀和+抽屉原理优化）
- 抽屉原理：如果询问的区间长度>=mod的话，一定有两个前缀和相减等于0，那么直接输出0即可
考试技巧：
我写的10 pts没加任何优化……抽屉原理送您80pts
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
ll x=0,f=1;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 n,m;
ll sum[500005];
int main()
{
freopen("input.txt","r",stdin);
scanf("%d%d",&n,&m);
rep(i,1,n)
sum[i]=sum[i-1]+read();
int l,r,mod;
rep(i,1,m)
{
l=read(),r=read(),mod=read();
if(r-l+1>mod)puts("0");//抽屉原理
else
{
int ans=mod;//相当于赋了一个极大值
rep(i,l,r)
rep(j,i,r)
ans=min((int)((sum[j]-sum[i-1])%mod),ans);
//强行转int
printf("%d\n",ans);
}
}
return 0;
}1385: 小奇回地球
二分 && dfs反向染色 && SPFA+判负环
解析
1.跑有负边图的最短路只能SPFA。
2.由于t和答案同增同减，具有单调性。我们可以二分t来取符合条件的最小距离。
3.问题出在对负环的处理上。一开始想的是，有负环直接判不合法。然而如果通过负环不能到达n号点，这个负环实际上可以忽略。所以开头建反边，从n跑dfs看能到达哪些点，只对这些点跑最短路即可。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int ans,n,m,cnt,mid;
int head[10000],used[105],dis[105],mark[105];
int read()
{
int x=0,f=1;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;
}
struct node{
int v,w,nxt;
}e[10000];
vector<int>G[105];
void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].nxt=head[u];
e[cnt].w=w;
head[u]=cnt;
}
int SPFA()
{
memset(used,0,sizeof(used));
rep(i,1,n)dis[i]=INT_MAX;
used[1]=1;
queue<int>Q;
Q.push(1);
dis[1]=0;
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(used[u]>n)
return false;//负环
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(!mark[v])continue;
int dist=e[i].w+mid;//要加上偏移量
if(dis[v]>dis[u]+dist)
{
dis[v]=dis[u]+dist;
used[v]++;
Q.push(v);
}
}
}
if(dis[n]>=0 && dis[n]!=INT_MAX)
return true;
else
return false;
}
void DFS(int cur)
{
mark[cur]=1;
for(int i=0;i<G[cur].size();i++)
{
if(mark[G[cur][i]])continue;
DFS(G[cur][i]);
}
}
int main()
{
freopen("input.txt","r",stdin);
int T;
T=read();
while(T--)
{
cnt=0;ans=-1;
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
memset(mark,0,sizeof(mark));
int l=-INT_MAX,r=INT_MAX;
n=read(),m=read();
rep(i,1,m)
{
int x,y,z;
x=read(),y=read(),z=read();
add(x,y,z);
G[y].push_back(x);
}
l=-100000,r=100000;
DFS(n);
while(l<=r)
{
mid=(l+r)>>1;
if(SPFA())
{
ans=dis[n];
r=mid-1;
}
else l=mid+1;
}
printf("%d\n",ans);
rep(i,1,n)G[i].clear();
}
return 0;
}