想了想还是打算用月报的方法来写题解，这样感觉没那么容易咕，也比一道题开个题解简略
毕竟有些题也没有那么神仙，没必要专门占用时间线
ABC227D - Project Planning
传送门
一句话题意
有N个部门，每个部门有Ai个人，
现有若干个跨部门计划，需要正好来自K个部门的K人，问最多可以实现多少个跨部门计划？
1≤K≤N≤2×105
1≤Ai≤1012
题解
考虑能否实现P个计划
令sum=∑i=1nmin(Ai,P)，如果PK>sum，那么显然不可能实现P个计划，否则可以实现。
证明：
如果有不小于K个Ai≥P，那么显然可以实现P个计划。否则，我们可以选择最大的K个Ai，将它们减小1来实现一个计划，从而每实现一个计划会使sum至多减少K，因而由PK≤sum，仍然可以实现P个计划
从而我们可以二分答案
复杂度O(nlogK∑(Ai))
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×m网格上有数字，要求从(1,1)出发走到(n,m)，每次只能向右或向下走。
走的花费是经过的所有格子上最大的K个数字之和
最小化花费
1≤H,W≤30
1≤K≤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
传送门
一句话题意
长度为n的序列未知，但知道序列上m个区间的按位或运算结果，保证序列上每个元素至少包含在一个区间内。求原序列所有子集的异或和之和，对1e9+7取模
1≤n,m≤200000
题解
若干个数的异或和的某一二进制位上为1，当且仅当这些数中在这一位上为1的数的个数为奇数。
考察原序列。显然在异或运算中各二进制位之间没有关系，故可以单独考察每一位二进制位对答案的贡献。设从低到高第i个二进制位上1的个数为si，那么这一位上0的个数就有n−si个。从这一二进制位上选择若干个数进行异或操作，结果为1的方案数即为从所有1中选出奇数个1的方案数，乘上任意选择0的方案个数，于是这一位对答案的贡献即为
\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.
于是将所有区间的按位或运算结果进行按位或运算，即可得到完整区间的按位或运算结果，从而得知每一二进制位上是否有1，根据上式进行计算即可
复杂度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,b和一个有理小数x的一部分x′，设x′的中的一个循环节长度为l，循环节在x′中出现的长度为p
例如，对于小数1.0285714285714的一个循环节857142，l=6,p=11(85714285714)
最大化a∗p−b∗l
题解
我们可以将小数部分提出，然后翻转。在所得串上求kmp的next数组，并枚举每一个前缀。对于某一个前缀si，p=i，l=i−next[i]
与答案取max即可。注意ans可能是负数，赋初值的时候要注意。进一步地，对于i=1一定有ans=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;
}
|
