【构造|2020牛客暑期多校训练营（第六场）解题报告BCEGHK】题目链接：https://ac.nowcoder.com/acm/contest/5671#question
B-Binary Vector
- 看样例可得
文章图片
,- 答案
文章图片
,只需要求一次2的逆元就够了
#include
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e7+10;
LL POW(LL x,LL y)
{
LL ans=1;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
LL inv(LL x){
return POW(x,mod-2);
}
LL a[N];
void init(){//预处理答案
LL inv2=inv(2);
LL ans=0,res=1,sum=inv2;
for(int i=1;
i>t;
while(t--){
int x;
cin>>x;
cout< C-Combination of Physics and Maths
- 一列一列的去找，因为两列合并时
文章图片
,即合并之后的值处于两者之间不超过较大值，那么就没有合并的意义了，一列一列的更新最大值。- 因为分母是选取的子矩阵的最后一行，因此可以扩大分子，即从第一行开始加到子矩阵末尾。
#include
using namespace std;
int a[205][205],b[205][205];
int main(){
int t;
scanf("%d",&t);
for(int i=0;
i E-Easy Construction
- 构造题。问1-n的排列是否能组成一个这样的序列，使得他同时存在长度为1-n的连续子序列，他们的和都满足sum%n=k%n
- 首先长度为n的子序列只有一个（它本身），那么sum=n*(n+1)/2,如果k不满足sum%n==k%n的话，直接输出-1
- n为奇数时，sum%n=0,那么就这么构造n,1,n-1,2,n-2...n/2,n/2+1
- n为偶数时，sum%n=n/2,那么就这么构造n,n/2,1,n-1,2,n-2...n/2-1,n/2+1
#include
using namespace std;
#define LL long long
int main(){
int n,k;
cin>>n>>k;
int sum=n*(n+1)/2;
if(sum%n!=k%n)cout<<-1< G-Grid Coloring
- 构造题。拿k种不同颜色 火柴拜访成n*n个正方形，必须满足：
- 每种颜色的火柴花的数量相同
- 一个正方形环上不能都是相同颜色的火柴
- 每行每列火柴不能全部相同
- n=1和k=1的情况肯定摆不出
- 可以按照从左到右依次1 2 3 4 5...摆放
- 如果n是k的倍数的话，如果还是从左到右扫描的话，那么左上角的正方形四条边都会是同样的颜色，不满足条件，所以另起一行是++tmp
- 如果n不是k的倍数的话，那么不影响
#include
using namespace std;
#define sc(a) scanf("%d",&a)
int n,k;
void color(){
int tmp=0;
if(n%k){
for(int i=1;
i<=(n+1)*2;
i++){
for(int j=1;
j<=n;
j++){
tmp=tmp%k+1;
cout< H-Harmony Pairs(数位dp)
- 题意：S(A)表示数字A的每一位数的和，S(24)=2+4=6，S(209)=2+0+9=11
- 求0到N中有多少对AB，使得S(A)>S(B) ，0<=A<=B<=N<=
文章图片
- 数位dp裸题，挺暴力的
- dp[pos][sum_delta][l1][l2]。
- 其中pos表示枚举到的下标
- sum_delta表示到pos之前AB的差值之和，为了避免出现负数，可以将其离散到1000
- l1表示A取数的上界
- l2表示B取数的上界
#include
using namespace std;
#define LL long long
#define sc(a) scanf("%d", &a)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
const int N = 1000;
const int mod = 1e9 + 7;
LL dp[105][2005][2][2];
char s[105];
int n;
LL dfs(int pos, int sum_delta, bool l1, bool l2)
{
if (pos == n + 1)//枚举到末尾
return sum_delta > N;
//说明S(较小数)>S(较大数)
if (~dp[pos][sum_delta][l1][l2]) //记忆化
return dp[pos][sum_delta][l1][l2];
int up1 = l1 ? s[pos] - '0' : 9;
//取上限
LL ans = 0;
for (int i = 0;
i <= up1;
i++) //枚举较大数
{
int up2 = l2 ? i : 9;
//取上限
for (int j = 0;
j <= up2;
j++) //枚举较小数
{
ans = (ans + dfs(pos + 1, sum_delta + j - i, l1 && i == up1, l2 && j == up2)) % mod;
}
}
dp[pos][sum_delta][l1][l2] = ans;
return ans;
}
int main()
{
ss(s + 1);
mem(dp, -1);
n = strlen(s + 1);
cout << dfs(1, N, true, true);
//离散化，将sum_delta初始化为1000，就不怕出现负数了
system("pause");
return 0;
} K-K-Bag
- K序列是由若干个大小为k的排列连接起来的排列
- 问给定的序列是否是K序列的子序列
- 定理：两个连续k排列之间设置断点，断点设置好之后，任意两个断点之间的距离都等于k。
- 首先判断一个数之后有多少个连续的不重复的数字，
- 然后再枚举所有可能成为第一个断点的位置，遍历之后的断点，查看是否能组成一个排列
- 由于k很大，这边需要进行离散化。
#include
using namespace std;
#define LL long long
#define sc(a) scanf("%d", &a)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
const int N = 1e6 + 5;
int a[N], b[N], vis[N], len[N];
//len存放的是从i开始之后连续不重复的数的个数
//vis标记i是否出现过
int main()
{
int t;
sc(t);
while (t--)
{
int n, k, f = 0;
sc(n);
sc(k);
for (int i = 1;
i <= n;
i++)
{
sc(a[i]);
b[i] = a[i];
if (a[i] > k) //当a[i]>k时，这个序列肯定不是k序列的子序列了
f = 1;
}
if (f)
{
cout << "NO" << endl;
continue;
}//离散化
sort(b + 1, b + n + 1);
int cnt = unique(b + 1, b + 1 + n) - (b + 1);
//去重
for (int i = 1;
i <= n;
i++)
{
a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
}
// for (int i = 1;
i <= n;
i++)
// {
//cout << a[i] << " ";
// }//记录长度
int i = 1, j = 1;
while (i <= n)
{
while (j <= n && !vis[a[j]])
vis[a[j++]]++;
vis[a[i]]--;
len[i] = j - i;
i++;
}int f1 = 0, end = min(k, 1 + len[1]);
for (int i = 1;
i <= end;
i++)
{
for (int j = i;
j <= n;
j += k)
{
if (j + len[j] - 1 == n) //表示断点设置成i的话，可以构成k序列
{
f1 = 1;
break;
}
else if (len[j] ^ k) //如果其中两个断点之间的距离不是k，说明断点设置错误
break;
}
if (f1)
break;
}
cout << (f1 ? "YES" : "NO") << endl;
}
system("pause");
return 0;
} 推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)
- 经典题|3462: DZY Loves Math II
- Android|【常用工具类】DensityUtils（dp px 互相转换）