想了想还是打算用月报的方法来写题解,这样感觉没那么容易咕,也比一道题开个题解简略

毕竟有些题也没有那么神仙,没必要专门占用时间线

ABC227D - Project Planning

传送门

一句话题意

NN个部门,每个部门有AiA_i个人,

现有若干个跨部门计划,需要正好来自KK个部门的KK人,问最多可以实现多少个跨部门计划?

1KN2×1051\le K \le N \le 2\times 10^5

1Ai10121\le A_i\le 10^{12}

题解

考虑能否实现PP个计划

sum=i=1nmin(Ai,P)sum=\sum_{i=1}^{n}min(A_i,P),如果PK>sumPK>sum,那么显然不可能实现PP个计划,否则可以实现。

证明:

如果有不小于KKAiPA_i\ge P,那么显然可以实现PP个计划。否则,我们可以选择最大的KKAiA_i,将它们减小11来实现一个计划,从而每实现一个计划会使sumsum至多减少KK​,因而由PKsumPK\le sum,仍然可以实现PP个计划

从而我们可以二分答案

复杂度O(nlog(Ai)K)O(n\log \frac{\sum(A_i)}{K})​​

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}

const int maxn=200000+100;
int n,K;
ll a[maxn];

bool Check(ll x)
{
ll sum=0;
for(int i=1;i<=n;++i)
sum+=min(a[i],x);
return K*x<=sum;
}

int main()
{
read(n),read(K);
ll l=0,r=0,ans=-1;
for(int i=1;i<=n;++i)
{
read(a[i]);
r+=a[i];
}
r/=K;
while(l<=r)
{
ll mid=(l+r)>>1;
if(Check(mid))
{
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
printf("%lld",ans);
return 0;
}

tag

二分答案

ABC227F - Treasure Hunting

传送门

一句话题意

n×mn\times m​网格上有数字,要求从(1,1)(1,1)出发走到(n,m)(n,m)​,每次只能向右或向下走。

走的花费是经过的所有格子上最大的KK个数字之和

最小化花费

1H,W301\le H,W\le 30

1KH+W1\le K \le H+W

题解

待填

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}

const ll inf=0x3f3f3f3f3f3f3f3f;
const int maxn=30+10;
const int maxK=maxn*2;
int n,m,K;
ll a[maxn][maxn];

int main()
{
read(n),read(m),read(K);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
read(a[i][j]);
ll ans=inf;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
ll dp[maxK][maxn][maxn];
memset(dp,0x3f,sizeof(dp));
if(a[1][1]>=a[i][j])
dp[1][1][1]=a[1][1];
if(a[1][1]<=a[i][j])
dp[0][1][1]=0;
for(int k=0;k<=K;++k)
for(int l=1;l<=n;++l)
for(int o=1;o<=m;++o)
{
if(l!=n)
{
if(k!=K && a[l+1][o]>=a[i][j])
dp[k+1][l+1][o] = min(dp[k+1][l+1][o],dp[k][l][o]+a[l+1][o]);
if(a[l+1][o]<=a[i][j])
dp[k][l+1][o] = min(dp[k][l+1][o],dp[k][l][o]);
}
if(o!=m)
{
if(k!=K && a[l][o+1]>=a[i][j])
dp[k+1][l][o+1] = min(dp[k+1][l][o+1],dp[k][l][o]+a[l][o+1]);
if(a[l][o+1]<=a[i][j])
dp[k][l][o+1] = min(dp[k][l][o+1],dp[k][l][o]);
}
}
ans=min(ans,dp[K][n][m]);
}
printf("%lld",ans);
return 0;
}

CF1614C - Divan and bitwise operations

传送门

一句话题意

长度为nn的序列未知,但知道序列上mm个区间的按位或运算结果,保证序列上每个元素至少包含在一个区间内。求原序列所有子集的异或和之和,对1e9+71e9+7取模

1n,m2000001\le n,m \le 200000

题解

若干个数的异或和的某一二进制位上为1,当且仅当这些数中在这一位上为11​的数的个数为奇数。

考察原序列。显然在异或运算中各二进制位之间没有关系,故可以单独考察每一位二进制位对答案的贡献。设从低到高第ii个二进制位上11的个数为sis_i,那么这一位上00的个数就有nsin-s_i个。从这一二进制位上选择若干个数进行异或操作,结果为11的方案数即为从所有11中选出奇数个11的方案数,乘上任意选择00的方案个数,于是这一位对答案的贡献即为

\left\{\begin{array} \\ 2^i\times2^{s_i-1}\times 2^{n-s_i}=2^i \times2^{n-1},s_i>0 \\ 0,s_i=0\end{array}\right.

于是将所有区间的按位或运算结果进行按位或运算,即可得到完整区间的按位或运算结果,从而得知每一二进制位上是否有11,根据上式进行计算即可

复杂度O(n)O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
t=0;ll f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}

const int maxn=200000+100;
const ll N = 200000;
const ll mod = 1e9+7;
ll T;
ll n,m;
ll pow2[N+1];

void Work()
{
read(n),read(m);
int OR=0;
for(int i=1;i<=m;++i)
{
int x;
read(x),read(x),read(x);
OR|=x;
}
ll ans=0,quan=1;
while(OR)
{
if(OR&1)
ans=(ans+quan*pow2[n-1]%mod)%mod;
quan<<=1;
OR>>=1;
}
printf("%lld\n",ans);
}

void Pre()
{
pow2[0]=1;
for(ll i=1;i<=N;++i)
{
pow2[i]=pow2[i-1]*2%mod;
}
}

int main()
{
Pre();
read(T);
while(T--)
{
Work();
}
return 0;
}

HDU6740 - MUV LUV EXTRA

传送门

这道题是CCPC2019秦皇岛站的L

一句话题意

给定a,ba,b​和一个有理小数xx​的一部分xx'​,设xx'​的中的一个循环节长度为ll​,循环节在xx'中出现的长度为pp

例如,对于小数1.02857142857141.0285714285714的一个循环节857142857142l=6,p=11(85714285714)l=6,p=11(85714285714)

最大化apbla*p-b*l

题解

我们可以将小数部分提出,然后翻转。在所得串上求kmp的next数组,并枚举每一个前缀。对于某一个前缀sis_ip=ip=il=inext[i]l=i-next[i]

与答案取maxmax即可。注意ansans可能是负数,赋初值的时候要注意。进一步地,对于i=1i=1一定有ans=abans=a-b

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}

const int maxlen=10000000+100;
ll a,b;
char s[maxlen],t[maxlen];
int len;
ll ans;
ll nxt[maxlen];

void GetNext()
{
nxt[1]=0;
int j=0;
for(int i=2;i<=len;++i)
{
while(j && t[i]!=t[j+1])
j=nxt[j];
if(t[i]==t[j+1])
++j;
nxt[i]=j;
ans=max(ans,a*i-b*(i-nxt[i]));
}
}

void Work()
{
ans=a-b;
scanf("%s",s+1);
len=strlen(s+1);
int tlen=0;
for(int i=len;i;--i)
{
if(s[i]=='.')
break;
t[++tlen]=s[i];
}
len=tlen;
GetNext();
printf("%lld\n",ans);
}

int main()
{
while(scanf("%lld%lld",&a,&b)!=EOF)
{
Work();
}
return 0;
}