期望得分：100+100+100=300
实际得分：0+100+90=190
T1 superman
二分给每条边加多少，判断是否存在负环
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 501
#define M 4951
using namespace std;
int n,tot,front[N],to[M],nxt[M],val[M],val_[M];
int front_[N],to_[M],nxt_[M];
int cnt[N],dis[N];
bool vis[N],ok[N];
void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val_[tot]=w;
to_[tot]=u; nxt_[tot]=front_[v]; front_[v]=tot;
}
bool spfa()
{
memset(cnt,,sizeof(cnt));
memset(dis,,sizeof(dis));
memset(vis,false,sizeof(vis));
queue<int>q;
vis[]=true; q.push();
dis[]=;
cnt[]++;
int now;
while(!q.empty())
{
now=q.front(); q.pop(); vis[now]=false;
for(int i=front[now];i;i=nxt[i])
{
if(!ok[to[i]]) continue;
if(dis[to[i]]>dis[now]+val[i])
{
dis[to[i]]=dis[now]+val[i];
if(!vis[to[i]])
{
vis[to[i]]=true;
q.push(to[i]);
cnt[to[i]]++;
if(cnt[to[i]]>n) return false;
}
}
} }
return dis[n]>=;
}
bool check(int mid)
{
for(int i=;i<=tot;i++) val[i]=val_[i]+mid;
return spfa();
}
void solve(int tmp)
{
for(int i=;i<=tot;i++) val[i]=val_[i]+tmp;
spfa();
printf("%d\n",dis[n]);
}
void dfs(int x)
{
ok[x]=true;
for(int i=front[x];i;i=nxt[i])
if(!ok[to[i]]) dfs(to[i]);
}
void dfs2(int x)
{
ok[x]=true;
for(int i=front_[x];i;i=nxt_[i])
if(!ok[to_[i]]) dfs2(to_[i]);
}
int main()
{
freopen("superman.in","r",stdin);
freopen("superman.out","w",stdout);
int T,m,u,v,w;
scanf("%d",&T);
while(T--)
{
tot=;
memset(front,,sizeof(front));
memset(front_,,sizeof(front_));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
memset(ok,false,sizeof(ok));
dfs();
if(!ok[n])
{
printf("-1\n");
continue;
}
memset(ok,false,sizeof(ok));
dfs2(n);
int l=-,r=,mid,tmp;
while(l<=r)
{
mid=(l+r)/;
if(check(mid)) tmp=mid,r=mid-;
else l=mid+;
}
solve(tmp);
}
}
T2 洛谷 P2647 最大收益
https://www.luogu.org/problem/show?pid=2647
如果一共选m个，第i个选了第j个物品，那对答案的贡献为wj-（m-i）*rj
所以如果确定选哪m个，肯定是先选rj小的
去除m的影响，倒着枚举
AC代码
#include<cstdio>
#include<algorithm>
#define N 3001
using namespace std;
struct node
{
int w,r;
}e[N];
int wi[N],ri[N],dp[N][N];
bool cmp(node p,node q)
{
return p.r>q.r;
}
int main()
{
//freopen("market.in","r",stdin);
//freopen("market.out","w",stdout);
int n,ans=;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d%d",&e[i].w,&e[i].r);
sort(e+,e+n+,cmp);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
dp[i][j]=max(dp[i-][j],dp[i-][j-]+e[i].w-e[i].r*(j-));
for(int i=;i<=n;i++) ans=max(ans,dp[n][i]);
printf("%d",ans); }
暴力1
#include<cstdio>
#include<algorithm>
#define N 3001
using namespace std;
struct node
{
int w,r;
}e[N];
int wi[N],ri[N],dp[N][N];
bool cmp(node p,node q)
{
return p.r<q.r;
}
int main()
{
int n,ans=;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d%d",&e[i].w,&e[i].r);
sort(e+,e+n+,cmp);
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
for(int j=;j<=min(i,k);j++)
dp[i][j]=max(dp[i-][j],dp[i-][j-]+e[i].w-(k-j)*e[i].r);
ans=max(ans,dp[n][k]);
}
printf("%d",ans); }
暴力2
#include<cstdio>
#include<algorithm>
#define N 3001
using namespace std;
struct node
{
int w,r;
}e[N];
int wi[N],ri[N];
bool cmp(node p,node q)
{
return p.r<q.r;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d%d",&wi[i],&ri[i]);
int S=<<n,tot=,tmp,ans=;
for(int i=;i<S;i++)
{
tot=;
for(int j=;j<n;j++)
if(i&(<<j)) e[++tot].w=wi[j],e[tot].r=ri[j];
sort(e+,e+tot+,cmp);
tmp=;
for(int j=;j<=tot;j++) tmp+=e[j].w-(tot-j)*e[j].r;
ans=max(ans,tmp);
}
printf("%d",ans);
}
T3 洛谷 P2759 奇怪的函数
x>=logx 10^(n-1)
x>=[log10 10^(n-1)]/log 10 x
x>=(n-1)/log10 x
特判当x=1时，答案为1
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
int n;
int main()
{
//freopen("Lemon_Soda.in","r",stdin);
//freopen("Lemon_Soda.out","w",stdout);
scanf("%d",&n);
LL l=,r=1ll<<,mid,ans;
if(n==)
{
printf("");
return ;
}
while(l<=r)
{
mid=l+r>>;
if((n-)*1.0/log10(mid)<=mid) r=mid-,ans=mid;
else l=mid+;
}
printf("%lld",ans);
}