期望得分：0+40+30=70
实际得分：0+10+10=20
题目修改：只能由0变1，只能用一次操作
大模拟
#include<cstdio>
#include<cstring>
using namespace std;
char s[];
int len,n;
int cnt[];
bool solve1()
{
if(len!=n) return false;
int num=;
for(int i=;i<len;i++)
if(s[i]=='') num+=i+;
if(num%(n+)==)
{
puts(s);
return true;
}
return false;
}
bool solve2()
{
if(len!=n) return false;
int num=;
for(int i=;i<len;i++)
if(s[i]=='') num+=i+;
for(int i=;i<len;i++)
if(s[i]=='')
{
num-=(i+);
if(num%(n+)==)
{
for(int j=;j<i;j++) putchar(s[j]);
putchar('');
for(int j=i+;j<len;j++) putchar(s[j]);
printf("\n");
return true;
}
num+=(i+);
}
return false;
}
bool solve3()
{
if(len<=n) return false;
int num=;
for(int i=;i<len;i++)
if(s[i]=='') num+=i+,cnt[i+]=cnt[i]+;
else cnt[i+]=cnt[i];
for(int i=;i<len;i++)
if(s[i]=='')
{
num-=(cnt[len]-cnt[i]);
if(num%(n+)==)
{
for(int j=;j<i;j++) putchar(s[j]);
for(int j=i+;j<len;j++) putchar(s[j]);
printf("\n");
return true;
}
num+=(cnt[len]-cnt[i]);
}
else
{
num-=(cnt[len]-cnt[i+]);
num-=(i+);
if(num%(n+)==)
{
for(int j=;j<i;j++) putchar(s[j]);
for(int j=i+;j<len;j++) putchar(s[j]);
printf("\n");
return true;
}
num+=(cnt[len]-cnt[i+]);
num+=(i+);
}
return false;
}
bool solve4()
{
if(len>=n) return false;
int num=;
for(int i=;i<len;i++)
if(s[i]=='') num+=(i+),cnt[i+]=cnt[i]+;
else cnt[i+]=cnt[i];
for(int i=;i<len;i++)
{
num+=cnt[len]-cnt[i];
if(num%(n+)==)
{
for(int j=;j<i;j++) putchar(s[j]);
putchar('');
for(int j=i;j<len;j++) putchar (s[j]);
printf("\n");
return true;
}
num+=i+;
if(num%(n+)==)
{
for(int j=;j<i;j++) putchar(s[j]);
putchar('');
for(int j=i;j<len;j++) putchar(s[j]);
printf("\n");
return true;
}
num-=(i+);
num-=(cnt[len]-cnt[i]);
}
if(num%(n+)==) { printf("%s",s); printf("0\n");return true; }
if((num+len+)%(n+)==) { printf("%s",s); printf("1\n"); return true; }
return false;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&n);
while(scanf("%s",s)!=EOF)
{
len=strlen(s);
if(solve1()) continue;
if(solve2()) continue;
if(solve3()) continue;
if(solve4()) continue;
printf("-1\n");
}
}
题目中要求选的数 %m 互不相同
那么可以很自然的想到
先在<m的数里选k个 ，使他们的和 s%m=n%m，那么还剩下n-s
为了保证%m 不相同，所以 我们把剩下的n-s 分为 （n-s）/m 个 m，
给这k个数分 m
也就是说
如果要换掉x，只能用和x 模m属于同一剩余系 的数换，所以 只能加 m的整数倍
设f[i][j] 表示选了i个数，和为j，且选的i个数互不相同的方案数
设g[i][j]表示把i个m分给j个数的方案数
那么ans= Σ f[i][j] * g[(n-j)/m][i] * i !, 其中要求j%m=n%m
这里要乘i的阶乘，因为 1 2 和 2 1 算作不同的方案
如何求f[i][j] ？
很容易想到 f[i][j][k] 表示 选了i个数，和为j，选的数字中最大的为k的方案数
这样是m^4，TLE
其实可以压去第三维
两维的缺陷是 如果顺序枚举i，枚举j，再枚举现在选哪个数，不能保证选的数%m互不相同
因为对于同一个数k，可能f[i+1][j] 由 已经选了k的f[i][j-k]再选k转移而来
解决的方法是
先枚举当前选哪个数，再倒序枚举选了多少个数，再枚举这些数的和
这样就保证了对于同一个数k，不会让 i+1 由 i 转移
如何求g[i][j]？
把i个东西分给j个人，显然是组合数
C（i+j-1，j-1）
难道 还要逆元？
其实不用 ，这个C 化开为：
1*2* …… i+j-1
---------------------------------（这是分数线）
（1*2……j-1）*（1*2……*i）
= （（i+1）*（i+2）……*（i+j-1））/（（j-1）！）
不要漏了 统计答案的时候还要乘上j！ 所以分母消去只剩下个j
求 （i+1）*（i+2）……*（i+j-1） 的时候，i 本身可能是 long long ，不要忘了先取模，防止 乘爆
#include<cstdio> #define M 101 using namespace std; typedef long long LL; const LL mod=; int f[M][M*M/]; LL mul(LL a,LL b)
{
LL res=;
for(LL i=a;i<=b;i++) res*=i,res%=mod;
return res;
} int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
LL n; int m;
scanf("%I64d%d",&n,&m);
int mx=m*(m-)/;
f[][]=;
for(int k=;k<m;k++)
for(int i=m;i;i--)
for(int j=k;j<=mx;j++)
f[i][j]+=f[i-][j-k],f[i][j]%=mod;
int x=n%m; LL res,ans=,y;
for(int i=x;i<=mx && i<=n;i+=m)
{
y=(n-i)/m;
for(int j=;j<=m;j++)
if(f[j][i])
{
res=mul((y+)%mod,(y+j-)%mod);
res*=f[j][i]; res%=mod;
res*=j; res%=mod;
ans+=res,ans%=mod;
}
}
printf("%I64d",ans);
}
解决本题的突破点：
哪一年种哪些地可以随意定
dp[i] 表示 种过的最右边的地为i时的最大收益
将所有的种地区间按左端点从左到右排序
那么对于当前这个种地区间[l[i],r[i]]
它的上一个种地区间 [l[j],r[j]],
l[j]一定<=l[i]
r[j]可能有三种情况
① r[j] < l[i] 此时第i块地 有全部的垦荒代价
② r[j]∈[l[i],r[i]) 此时第i块地 有 右边部分的垦荒代价
③ r[j]>=r[i] 此时第i块地 没有垦荒代价
令sum[i]表示垦荒代价的前缀和，val[i]表示第i次垦荒的收益
那么对应的状态转移方程：
① dp[r[i]]=max(dp[r[j]]+val[i]-（sum[r[i]]-sum[l[i]-1]）)
② dp[r[i]]]=max(dp[r[j]]+val[i]-（sum[r[i]]-sum[r[j]]）)
③ dp[r[j]]+=val[i]
朴素的dp为O（n^2）
可用线段树优化至nlogn
在 r[j]==r[i] 时，有很多细节
线段树的没调出来
30分 n^2代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> #define N 200001 using namespace std; typedef long long LL; LL sum[N],dp[N];
int vis[N]; struct node
{
int l,r,p;
}e[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q)
{
if(p.l!=q.l) return p.l<q.l;
return p.r<q.r;
} int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
int n,m,x;
read(n); read(m);
for(int i=;i<=n;++i) read(x),sum[i]=sum[i-]+x;
for(int i=;i<=m;++i) read(e[i].l),read(e[i].r),read(e[i].p);
sort(e+,e+m+,cmp);
memset(dp,-,sizeof(dp));
for(int i=;i<=m;i++)
{
LL tmp=-1e18; bool ok=false;
dp[e[i].r]=max(dp[e[i].r],e[i].p-(sum[e[i].r]-sum[e[i].l-]));
tmp=dp[e[i].r];
for(int j=i-;j;j--)
if(e[j].r<e[i].l) dp[e[i].r]=max(dp[e[i].r],dp[e[j].r]+e[i].p-(sum[e[i].r]-sum[e[i].l-]));
else if(e[j].r<e[i].r) dp[e[i].r]=max(dp[e[i].r],dp[e[j].r]+e[i].p-(sum[e[i].r]-sum[e[j].r]));
else if(vis[e[j].r]!=i) // 一个e[i].p只能累计一次到一个e[j].r 里
{
if(e[j].r==e[i].r) ok=true;//e[i].r==e[j].r 时，r 可能被 前两种情况修改过，但累计的话只能是用没有修改过的
else dp[e[j].r]+=e[i].p,vis[e[j].r]=i;
}
if(ok) dp[e[i].r]=max(dp[e[i].r],tmp+e[i].p);
}
LL ans=;
for(int i=;i<=n;i++) ans=max(ans,dp[i]);
printf("%I64d",ans);
}
std
#include <cstdio>
#include <cctype>
#include <memory.h>
#include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif int nextInt() {
int s = , d;
bool nag = ;
do {
d = getchar();
if (d == '-')
nag = ;
} while (!isdigit(d));
do
s = s * + d - , d = getchar();
while (isdigit(d));
return nag ? -s : s;
} struct seg {
int l, r;
qw v, z;
seg *ls, *rs;
};
struct obj {
int l, r, v;
}; inline bool cmpObj(const obj& a, const obj& b) {
return (a. l < b. l) || (a. l == b. l && a. r < b. r);
} const int maxn = ;
const qw inf = 0x3f3f3f3f3f3f3f3fLL; int n, m;
obj q[maxn];
qw s[maxn], ans;
seg *rtf, *rtc, *sp; #define mid(p) ((p->l+p->r)>>1) seg *sgtBuild(int l, int r) {
seg *p = sp ++;
p-> v = - inf;
p-> z = ;
p-> l = l;
p-> r = r;
if (l + < r) {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
}
return p;
} void sgtChg(seg* p, int p0, qw v0) {
if (p-> l + == p-> r)
p-> v = max(p-> v, v0);
else {
if (p0 < mid(p))
sgtChg(p-> ls, p0, v0 - p-> z);
else
sgtChg(p-> rs, p0, v0 - p-> z);
p-> v = max(p-> ls-> v, p-> rs-> v) + p-> z;
}
} qw sgtQry(seg* p, int l, int r) {
if (l >= r)
return -inf;
else if (p-> l == l && p-> r == r)
return p-> v;
else if (r <= mid(p))
return sgtQry(p-> ls, l, r) + p-> z;
else if (l >= mid(p))
return sgtQry(p-> rs, l, r) + p-> z;
else
return max(sgtQry(p-> ls, l, mid(p)), sgtQry(p-> rs, mid(p), r)) + p-> z;
} void sgtLazy(seg* p, int l, qw z0) {
if (p-> v == -inf)
return;
else if (p-> l == l)
p-> v += z0, p-> z += z0;
else {
if (l < mid(p)) {
sgtLazy(p-> ls, l, z0);
sgtLazy(p-> rs, mid(p), z0);
}
else
sgtLazy(p-> rs, l, z0);
p-> v = max(p-> ls-> v, p-> rs-> v) + p-> z;
}
} int main() {
// freopen("c.in","r",stdin);
// freopen("c.out","w",stdout);
sp = new seg[maxn * ];
n = nextInt();
m = nextInt();
rtf = sgtBuild(, n + );
rtc = sgtBuild(, n + );
s[] = ;
for (int i = ; i <= n; i ++)
s[i] = s[i - ] + nextInt();
for (int i = ; i < m; i ++) {
q[i]. l = nextInt();
q[i]. r = nextInt();
q[i]. v = nextInt();
}
sort(q, q + m, cmpObj);
ans = ;
for (int i = ; i < m; i ++) {
qw res0 = max(sgtQry(rtf, , q[i]. l), 0LL) - s[q[i]. r] + s[q[i]. l - ];
qw res1 = sgtQry(rtc, q[i]. l, q[i]. r + ) - s[q[i]. r];
qw res = max(max(res0, res1), sgtQry(rtf, q[i]. r, n + )) + q[i]. v;
sgtLazy(rtf, q[i]. r, q[i]. v);
sgtLazy(rtc, q[i]. r, q[i]. v);
sgtChg(rtf, q[i]. r, res);
sgtChg(rtc, q[i]. r, res + s[q[i]. r]);
ans = max(ans, res);
printf("%I64d %I64d\n",res,ans);
}
printf(lld "\n", ans);
}
没跳出来&&不想调的线段树
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> #define N 200001 using namespace std; typedef long long LL; LL sum[N]; LL mx1[N<<],mx2[N<<],f[N<<]; LL t1,t2; struct node
{
int l,r,p;
}e[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q)
{
if(p.l!=q.l) return p.l<q.l;
return p.r<q.r;
} void change(int k,int l,int r,int pos,LL w,int ty)
{
if(l==r)
{
if(ty==) mx1[k]=max(mx1[k],w);
else mx2[k]=max(mx2[k],w);
return;
}
int mid=l+r>>;
if(pos<=mid) change(k<<,l,mid,pos,w,ty);
else change(k<<|,mid+,r,pos,w,ty);
mx1[k]=max(mx1[k<<],mx1[k<<|])+f[k];
mx2[k]=max(mx2[k<<],mx2[k<<|])+f[k];
} int query(int k,int l,int r,int opl,int opr,int ty)
{
if(l>=opl && r<=opr)
{
if(ty==) return max(t1,mx1[k]);
return max(t2,mx2[k])a;
}
int mid=l+r>>;
if(opr<=mid) return query(k<<,l,mid,opl,opr,ty)+f[k];
if(opr>mid) return query(k<<|,mid+,r,opl,opr,ty)+f[k];
return max(query(k<<,l,mid,opl,opr,ty),query(k<<|,mid+,r,opl,opr,ty))+f[k];
} void add(int k,int l,int r,int pos,int w)
{
if(l==pos)
{
f[k]+=w;
mx1[k]+=w;
mx2[k]+=w;
return;
}
int mid=l+r>>;
if(pos<=mid) add(k<<,l,mid,pos,w),add(k<<|,mid+,r,mid+,w);
else add(k<<|,mid+,r,pos,w);
mx1[k]=max(mx1[k<<],mx1[k<<|])+f[k];
mx2[k]=max(mx2[k<<],mx2[k<<|])+f[k];
} int main()
{
// freopen("8.in","r",stdin);
// freopen("c.out","w",stdout);
int n,m,x; LL ans=;
read(n); read(m);
for(int i=;i<=n;++i) read(x),sum[i]=sum[i-]+x;
for(int i=;i<=m;++i)
read(e[i].l),read(e[i].r),read(e[i].p);
sort(e+,e+m+,cmp);
memset(mx2,-,sizeof(mx2));
memset(mx1,-,sizeof(mx1));
LL now;
for(int i=;i<=m;i++)
{
t1=query(,,n,e[i].l,e[i].r,);//2
t2=query(,,n,e[i].r,n,);
now=t1+e[i].p-sum[e[i].r];//
now=max(now,t2+e[i].p);
t2=query(,,n,,e[i].l,);
now=max(now,t2+e[i].p-sum[e[i].r]+sum[e[i].l-]);//
ans=max(ans,now);
add(,,n,e[i].r,e[i].p);
change(,,n,e[i].r,now+sum[e[i].r],);
change(,,n,e[i].r,now,); printf("%I64d %I64d\n",now,ans);
}
printf("%I64d",ans);
}