//yy：拒绝转载！！！
悄悄告诉你，做题累了，去打两把斗地主就能恢复了喔~~~
//yy：可是我不会斗地主吖(〃'▽'〃)
~~~那就听两遍小苹果嘛~~~
五一假期除了花时间建模，就抽空把最近没做的CF题补了点。。毕竟明天开始又要继续上好多课呐。。。Yes, I can!(ง •_•)ง……（I can Huá shuǐ~~）
codeforces 803 A. Maximal Binary Matrix 【简单构造】
题意：n行和n列填充零矩阵。 您要将k个1放在其中，使得得到的矩阵相对于主对角线（从左上角到右下角的对角线）是对称的，并且是词典上最大的。如果不存在这样的矩阵，则输出-1。
例如这样的：
Input
3 6
Output
1 1 1
1 1 0
1 0 0
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
int n, k;
int a[][];
int main() {
int i, j;
scanf("%d%d", &n, &k);
CLR(a, );
if(k > n*n) {printf("-1\n"); return ;}
for(i = ; i < n; ++i) {
if(k) {a[i][i] = ; k--;}
for(j = i+; j < n; ++j) {
if(k >= ) {
a[i][j] = a[j][i] = ;
k -= ;
}
}
}
for(i = ; i < n; ++i){
for(j = ; j < n-; ++j) {
printf("%d ", a[i][j]);
}
printf("%d\n", a[i][j]);
}
return ;
}
codeforces 803 B. Distances to Zero 【暴力】
题意：给出整数数组a0，a1，...，an-1的数组。对于每个元素，找到其和最近的零的距离（对于等于零的元素）。 给定数组中至少有一个零元素。
题解：暴力，顺的和逆的分别找最近距离并更新
//yy:那天比赛时做完这题就睡觉了orz
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
const int N = 2e5+;
const int inf = 0x3f3f3f3f;
int n, k;
int a[N], b[N], c[N];
int main() {
int i, j;
int cnt = ;
scanf("%d", &n);
CLR(c, inf);
for(i = ; i < n; ++i) {
scanf("%d", &a[i]);
if(a[i]==) {b[cnt++] = i;c[i] = ;}
}
for(i = j = ; i < cnt && j <n; ++i) {
for(; j < b[i]; ++j) {
c[j] = min(b[i]-j, c[j]);
}
}
for(i = cnt-, j = n - ; i >= && j >= ; --i) {
for(; j > b[i]; --j) {
c[j] = min(c[j], j-b[i]);
}
}
for(i = ; i < n-; ++i)
printf("%d ", c[i]);
printf("%d\n", c[n-]);
return ;
}
题意：已知正整数n。 你要创建k个正数a1，a2，...，ak（严格增加的序列），它们的和等于n，最大公因数是最大的。
（序列的最大公约数是这样的数字的最大值，即序列的每个元素都可以被它们整除。）如果没有可能的序列，则输出-1。
题解：
//yy：开始看这题看着数字就头疼，后来补题，补完后心情很好喔ヾ(๑╹◡╹)ﾉ"
//构造：ma,2*ma,3*ma……(k-1)*ma, n-sum, sum为前k-1项的和
//高斯算法，sum = （首+尾）/2*项数 = (k-1)*k*ma / 2
//关于求最大公约数ma… ①n % ma = 0;
② k*(k+1)*ma/2 <= n => k*(k+1)/2 <= n/ma
// 最后一项： n – sum = n – (k-1)*k*ma/2
//输出为-1的情况：k*(k+1)/2>n或k>2e5
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, k;
int main() {
scanf("%lld%lld", &n, &k);
if(k*(k+)/ > n || k >= 200000) {printf("-1\n"); return ;}
ll ma = ;
for(ll i = ; i*i <= n; ++i) {
if(n % i == ) {
if(n/i >= k*(k+)/) ma = max(ma, i);
if(i >= k*(k+)/) ma = max(ma, n/i);
}
}
for(ll i = ; i < k; ++i) {
printf("%lld ", i*ma);
}
printf("%lld\n", n-(k-)*k*ma/);
return ;
}
codeforces 803 D. Magazine Ad 【二分】
题意：有空格分隔的非空字母的小写和大写拉丁字母。
有连字符'”-“，他们的位置设置了字词换行点。 单词可以包含多个连字符。（保证没有相邻的空格，没有相邻的连字符。 没有连字符与空格相邻。 在第一个单词和最后一个单词之后，没有空格，没有连字符。）
当单词被包裹时，单词之前的连字符的部分和连字符本身保持在当前行上，并且该单词的下一部分放在下一行上。
也可以在两个单词之间设置换行符，在这种情况下，空格停留在当前行上。
该广告占用行数 ≤ k 行，并且应该具有最小的宽度。 广告的宽度是字符串的最大长度（字母，空格和连字符）。
求广告的最小宽度。
//yy:谷歌翻译，你，值得拥有~
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
const int N = 1e6+;
int k, len;
char s[N];
int f(int m) {
int cnt = ;//行数
int x = , last = -;
for(int i = ; i < len; ++i) {
if(s[i] == ' ' || s[i] == '-')
last = i;//词尾标记
if(i == len-) last = i;
x++;
if(x >= m) {cnt++; x = i-last;}
if(x >= m) return ;
}
if(x) cnt++;
return cnt <= k;
}
int main() {
scanf("%d ", &k);
gets(s);
len = strlen(s);
int l = , r = len;
while(l < r) {
int mid = (l+r)>>;
if(f(mid)) r = mid;
else l = mid + ;
}
printf("%d\n", l);
return ;
}
这一套题后面补不动了orz，因为看着下一题标签是DP就很烦不想看了。。。
~~~~~~~~~~~~~~~~_(:з」∠)_我的床需要我~~~~~~~~~~~~~~~
codeforces 801 A. Vicious Keyboard 【暴力】
题意：给一串字符，求“VK”出现的最多次数，允许最多修改一个字符
题解：暴力，直接用string的find查找，很方便哦~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
string s;
int main() {
cin >> s;
int i = , cnt = ;
int len = s.size();
while((i = s.find("VK")) != -) {
s[i] = s[i+] = '.';
cnt++;
}
if(s.find("VV") != - ||s.find("KK") != -)
cnt++;
printf("%d\n", cnt);
return ;
}
不用find的话，就这样暴力吧。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
string s;
int main() {
cin >> s;
int i, cnt = ;
int len = s.size();
s += 'a';
int f = ;
for(i = ; i < len-; ++i) {
if(s[i] == 'V' && s[i+] == 'K') {cnt++; i++;continue;}
if(f) continue;
if(s[i] == 'V' && s[i+] == 'V' && s[i+] != 'K') f = ;
else if(s[i] == 'K' && s[i+] == 'K') f = ;
}
printf("%d\n", cnt+(f==));
return ;
}
codeforces 801 B. Valued Keys 【水】
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = ;
char a[N], b[N];
int main() {
scanf("%s %s", a, b);
int f = ;
int len = strlen(a);
for(int i = ; i < len; ++i)
if(a[i] < b[i]) {
f = ;
break;
}
if(f) puts("-1");
else puts(b);
return ;
}
~~~~~~~~~~~~~~~~~~~(:[___] 露眼睡~~~~~~~~~~~~~~~~~
codeforces 798 A. Mike and palindrome 【水】
题意：改变一个字符能否使字符串变为回文串
//yy：第一遍读题不仔细，以为不改变字符也可以，结果…我，我，wa~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = ;
char a[N];
int main() {
scanf("%s", a);
int len = strlen(a);
int cnt = ;
for(int i = ; i < len/; ++i) {
if(a[i] != a[len--i])
cnt++;
}
if(cnt > || !cnt && len % == ) puts("NO");
else puts("YES");
return ;
}
codeforces 798 B. Mike and strings 【暴力】
题意：给n个字符串，每次可以把一个字符串的第一个字母移到最后，问最少移动几次可以使n个字符串完全相等。
题解：暴力，每次选定一个字符串作为最终结果，把要移动的字符串复制一遍，再find很方便哦~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = ;
string a[N], b[N];
int main() {
int n, i, j;
scanf("%d", &n);
for(int i = ; i < n; ++i) {
cin >> a[i];
b[i] = a[i] + a[i];
}
int cnt = , mi = inf, x = ;
for(i = ; i < n; ++i) {
cnt = ;
for(j = ; j < n; ++j) {
if((x = b[j].find(a[i])) == -) {puts("-1"); return ;}
cnt += x;
}
mi = min(mi, cnt);
}
printf("%d\n", mi);
return ;
}
codeforces 798 C. Mike and gcd problem
题意：每次可以删除 ai, ai + 1 然后把 ai - ai + 1, ai + ai + 1放回原位，求最小次数使得数组所有数的最大公约数大于1
题解：把所有奇数改成偶数即可。。。我居然没想到orz
连续两个奇数改一次即可，一个奇数一个偶数要改两次
//yy：其实一开始我还是有疑问的，题目说gcd(0,2)=2，0怎么可以求最大公约数啊(-_-)ゞ
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5+;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll a[N];
int main() {
int n, i, j;
scanf("%d", &n);
ll t = ;
for(i = ; i < n; ++i) {
scanf("%lld", &a[i]);
t = gcd(t, a[i]);
}
if(t > ) {puts("YES\n0\n"); return ;}
int ans = ;
for(i = ; i < n; i++) {
if(a[i] % == ) {
ans++;
if(a[++i] % == ) ans++;
}
}
printf("YES\n%d\n", ans);
return ;
}
codeforces 798 D. Mike and distribution
题意：让你选择k 个数 组成序列：P = [p1, p2, ..., pk] （ 1 ≤ pi ≤ n ， 1 ≤ i ≤ k ）并且序列中的元素都不同。满足： 2·(ap1 + ... + apk) 大于A数组的所有元素之和，2·(bp1 + ... + bpk) 大于B数组所有元素之和。并且k≤ 
题解：第一遍做的时候，我先将下标以A的大小顺序来排序，若n为奇数，则k=n/2+1，先选取第一个下标，再两个两个的根据B数组的数的大小来选取下标；若n为偶数，则k = n/2，再两个两个选取下标，但是错了哦WA，因为题目说了是大于元素之和，我这样写是大于等于。。。正解：排序照旧，k直接取n/2+1，然后就没有然后了，详见代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 1e5+;
int a[N], b[N], p[N];
bool cmp(int x, int y) {
return a[x] > a[y];
}
int main() {
int n, i, j;
scanf("%d", &n);
for(i = ; i < n; ++i) scanf("%d", &a[i]);
for(i = ; i < n; ++i) scanf("%d", &b[i]); for(i = ; i < n; ++i) p[i] = i; //下标
sort(p, p+n, cmp); printf("%d\n%d ", n/+, p[]+);
for(i = ; i < n-; i += ) {
if(b[p[i]] > b[p[i+]]) printf("%d ", p[i]+);
else printf("%d ", p[i+]+);
}
if(i == n-) printf("%d", p[n-]+);
return ;
}
~~~~~~~~~~~~~~~(|3[____] 睡的很死..~~~~~~~~~~~~~~~
~~~补西电校赛一道水题：
xidian 1200: Hanoi Tower – SetariaViridis 【快速幂】
普通的汉诺塔是2^n-1，这里乘个2就行了。为什么呢为什么呢(O_O)?
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
ll p = ;
ll pow_mod(ll a, ll b) {
ll r = ;
while(b) {
if(b&) r = (r*a)%p;
a = (a*a)%p;
b >>= ;
}
return r;
}
int main() {
ll n;
while(~scanf("%lld", &n))
printf("%lld\n", ((pow_mod(,n)-)*)%p);
return ;
}
~~~~~~~马拉松24
//yy：题目今天还没挂出来，直接贴上房教的代码~(￣▽￣)~*
#include<stdio.h>
using namespace std;
#define mem(a,b); memset(a,b,sizeof(a));
#define scan(a); scanf("%d",&a);
typedef long long ll;
const ll mod = 1e9+;
const int maxn = 1e6+;
int main()
{
int n;
scan(n);
ll a = ll(n)*(n-)/*;
if(a%(n-)) return *printf("0\n");
int ans=a/(n-); for(int i=;i<=n-;i++)
{
if(i>) printf(" ");
printf("%d",i);
}
printf("\n");
int pre = ans - n;
printf("%d",pre);
for(int i=;i<n-;i++)
{
printf(" ");
printf("%d",ans-i-pre);
pre = ans-i-pre; }
printf("\n");
return ;
}
//yy：写完博客刚好熄灯｡◕ᴗ◕｡