P101
zhx
a
【问题描述】
你是能看到第一题的 friends 呢。
——hja
Hja 拥有一套时光穿梭技术，能把字符串以超越光速的速度传播，但是唯一
的问题是可能会 GG。在传输的过程中，可能有四种情况：
1、字符串没有发生改变。
2、字符串的某一位由 0 变 1 或者由 1 变 0。
3、某一位消失了。
4、多了一位。
为了防止字符串 GG，Hja 保证发送的字符串只由 01 组成，并且所有字符
串开始的长度均为?，并且所有为 1 的位置的下标之和一定是? + 1的倍数。在
给定了你这些条件之后，Hja 告诉你传输之后的字符串，并按照以下规则复原
字符串：
1、对于一个字符串，按照四种规则从前到后的优先级依次尝试能否复原为
一个合法的字符串。
2、对于同一种操作，更靠前的位置更加优先。
3、对于同一种操作的同一位置，0 比 1 更加优先。
4、如果没有任何一种方法复原字符串，则输出−1。
【输入格式】
第一行一个整数?，代表所有字符串的长度。
接下来若干行，每行一个字符串。
【输出格式】
对于每个字符串，输出一行代表答案。
【样例输入】
4
0000
011
1011
11011
【样例输出】
0000
0110
1001
1111
【数据范围与规定】
对于100%的数据，4 ≤ ? ≤ 1000，字符串数量不超过3000。
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100000
using namespace std;
int mod,pos[maxn],cnt,del[maxn],w[maxn],sum[maxn];
string s;
bool f;
int n,len,l;
void dfs(int len,int Sum,int t){
if(f)return;
if(len==n&&Sum%mod==){
for(int i=;i<l;i++){
if(del[i])continue;
printf("%c",s[i]);
}
printf("\n");
f=;
return;
}if(t)return;
if(len==n)return;
for(int i=;i<l;i++){
if(!del[i]){
del[i]=;
if(s[i]==''){
dfs(len-,Sum-w[i],);if(f)return;
}
if(s[i]==''){
dfs(len-,Sum-(i+)-w[i+],);if(f)return;
}
del[i]=;
}
}
}
void dfs1(int c,int Sum,int t){
if(f)return; if(Sum%mod==){
cout<<s<<endl;
f=;
return;
}if(t)return;
if(c==)return;
for(int i=;i<=cnt;i++){
if(!del[pos[i]-]){
del[pos[i]-]=;
s[pos[i]-]='';
dfs1(c-,Sum-pos[i],);
del[pos[i]-]=;
s[pos[i]-]='';
}
} }
int main(){
//freopen("Cola.txt","r",stdin);
freopen("a.in","r",stdin);freopen("a.out","w",stdout);
scanf("%d",&n);
mod=n+;
while(cin>>s){
memset(del,,sizeof(del));
memset(w,,sizeof(w));
f=;
cnt=;
l=len=s.length();
int Sum=;
for(int i=;i<len;i++)
if(s[i]==''){
pos[++cnt]=i+;
Sum+=i+;
}
for(int i=l-;i>=;i--){
if(s[i]=='')w[i]=w[i+]+;
else w[i]=w[i+];
}
if(len==n){//一定是1,2操作
if(Sum%mod==){
cout<<s<<endl;
continue;
}
bool flag=;
dfs1(cnt,Sum,);
if(!f) printf("-1\n");
continue;
}
if(len>n){//删掉几位
if(len-n>){
printf("-1\n");
continue;
}
f=;
dfs(len,Sum,);
if(!f)printf("-1\n");
continue;
}
if(len<n){//加上几位
if(n-len>){
printf("-1\n");
continue;
}
int num=;
for(int i=len-;i>=;i--){
if(s[i]=='') num+=i+;
sum[i]=sum[i+]+(s[i]==''?:);
}
int ans=num%(n+),flag=;
for(int i=;i<=len;i++){
if((sum[i]+ans)%(n+)==){
for(int j=;j<len;j++)
if(j!=i) cout<<s[j];
else if(i!=len) cout<<""<<s[j];
if(i==len) cout<<"";
flag=;
break;
}
if((sum[i]+ans+i+)%(n+)==){
for(int j=;j<len;j++)
if(j!=i) cout<<s[j];
else if(i!=len) cout<<""<<s[j];
if(i==len) cout<<"";
flag=;
break;
}
}
if(!flag) cout<<"-1";
printf("\n");
}
}
fclose(stdin);fclose(stdout);
return ;
}
100分 模拟
b
【问题描述】
你是能看到第二题的 friends 呢。
——laekov
Hja 和 Yjq 在玩游戏，这个游戏中 Hja 给了 Yjq 两个数?,?，希望 Yjq 找到
一些非负整数使得这些数的和等于?，并且所有数模?的值互不相同，求方案
数。
【输入格式】
一行两个整数?,?。
【输出格式】
一行一个整数代表答案对905229641取模之后的结果。
【样例输入 1】
3 3
【样例输出 1】
9
【样例输入 2】
523 44
【样例输出 2】
338398304
【数据范围与规定】
220,? ≤ 5。
4300,? ≤ 10。
70%的数据，? ≤ 10 18 ,? ≤ 20。
对于100%的数据，? ≤ 10 18 ,? ≤ 100。
#include<iostream>
#include<cstdio>
#define mod 905229641
using namespace std;
long long n,limit,sm[];
int m,ans;
void dfs(int yu,long long res,int use){
if(res==){
ans=(ans+sm[use])%mod;
return;
}
if(yu==m)return;
if(res<)return;
dfs(yu+,res,use);
for(int i=;i<=limit;i++)
dfs(yu+,res-(i*m+yu),use+);
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("b.in","r",stdin);freopen("b.out","w",stdout);
sm[]=;
for(int i=;i<=;i++)sm[i]=sm[i-]*i%mod;
cin>>n>>m;
limit=n/m;
dfs(,n,);
printf("%d",ans);
fclose(stdin);fclose(stdout);
return ;
}
20分 暴力
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm> using namespace std; #ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif const int maxn=;
const int maxs=maxn*maxn/;
const int mo=; long long n; int m,f[maxn][maxs],fac[maxn]; int calc(long long a,long long b)
{
long long ans=;
for (int c=;c<a;c++)
ans=ans*(b+c)%mo;
return (int)ans;
} int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout); scanf(LL "%d",&n,&m);
f[][]=;
int up=m*(m-)/;
for (int a=;a<m;a++)
for (int b=m;b>=;b--)
for (int c=up;c>=;c--)
if (f[b][c]) f[b+][c+a]=(f[b+][c+a]+f[b][c])%mo;
fac[]=;
for (int a=;a<=m;a++)
fac[a]=(long long)fac[a-]*a%mo;
int x=(int)(n%m);
int ans=;
for (int a=x;a<=n && a<=up;a+=m)
{
long long rest=(n-a)/m;
for (int b=;b<=m;b++)
if (f[b][a])
{
int nowans=calc(b,rest%mo);
nowans=(long long)nowans*f[b][a]%mo;
nowans=(long long)nowans*b%mo;
ans=(ans+nowans)%mo;
}
}
printf("%d\n",ans); return ;
}
100分
c
【问题描述】
你是能看到第三题的 friends 呢。
——aoao
Hja 回到老家开始种地，由于太久没有种地，所以所有地都是荒地。将每片
地从荒地变成不荒地有一定的代价， 但是一旦改变之后就不再是荒地了。 现在Hja
要开始?年的种地生活，第?年 Hja 可以在? ? 到? ? 块地上种地，并且可以获得? ? 的
收益。 （注意，要种地必须整段一起种，并且这些地一定已经是不荒地）Hja 可以
选择种或者不种每一年的地，问 Hja 能够获得的最大收益。
【输入格式】
第一行两个整数?,?，代表地的数量和年数。
一行?个数，代表每块地变成不荒地的代价。
接下来?行，每行三个整数? ? ,? ? ,? ? 如题意描述。
【输出格式】
一行一个整数代表答案。
【样例输入】
7 4
3 2 3 2 1 2 3
1 2 5
2 3 5
3 5 3
7 7 5
【样例输出】
4
【数据规模与约定】
30%的数据，1 ≤ ?,? ≤ 100。
对于100%的数据，1 ≤ ?,? ≤ 100000。
#include<iostream>
#include<cstdio>
#define maxn 100010
using namespace std;
int n,m,w[maxn],ans=,a[maxn*],cnt;
struct node{
int l,r,v;
}p[maxn];
void dfs(int now,int sum){
if(now==m+){
ans=max(ans,sum);
return;
}
dfs(now+,sum);
int due=;
int pos=cnt+;
for(int i=p[now].l;i<=p[now].r;i++)due+=w[i],a[++cnt]=w[i],w[i]=;
dfs(now+,sum-due+p[now].v);
for(int i=p[now].l,j=pos;i<=p[now].r;i++,j++)w[i]=a[j];
cnt=pos-;
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("c.in","r",stdin);freopen("c.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&w[i]);
for(int i=;i<=m;i++)
scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].v);
dfs(,);
cout<<ans;
fclose(stdin);fclose(stdout);
return ;
}
10分 暴力
#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(lld "\n", ans);
}
100分