题目链接：
https://codeforces.com/contest/1118
A题：
题意：
q次查询，给你一个n，要你用1和2来凑出n，1的花费为a，2的花费为b，求花费的最小值。
思路：
我们知道当2*a<=b时全用1来肯定是最优的，当2*a>b时，若n为奇数就是1个1其他全是2，若n为偶数就全都是2这样是最优的。
代码实现如下：
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL; #define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-;
const int mod = ;
const int maxn = 2e5 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL; int q;
LL n, a, b; int main(){
scanf("%d", &q);
while(q--) {
scanf("%lld%lld%lld", &n, &a, &b);
LL ans = ;
if( * a <= b) {
ans = n * a;
} else {
ans = n / * b + (n % ) * a;
}
printf("%lld\n", ans);
}
return ;
}
B题：
题意：
给你n个数，要你去掉一个数，然后剩余的n-1个数保持相对顺序不变，问有多少种方案使得剩下的数中奇数项的和等于偶数项的和。
思路：
我们知道去掉一个数后对前面的数的位置的奇偶性不会产生影响，后面的数的位置的奇偶性变为对立的，因此我们只需要求下奇数项和偶数项的前缀和即可。
代码实现如下：
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL; #define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-;
const int mod = ;
const int maxn = 2e5 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL; int n;
LL a[maxn], sum1[maxn], sum2[maxn]; int main(){
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%lld", &a[i]);
sum1[i] = sum1[i-];
sum2[i] = sum2[i-];
if(i & ) sum1[i] += a[i];
else sum2[i] += a[i];
}
int ans = ;
for(int i = ; i <= n; i++) {
if(sum1[i-] + sum2[n] - sum2[i] == sum2[i-] + sum1[n] - sum1[i]) {
ans++;
}
}
printf("%d\n", ans);
return ;
}
C题：
题意：
给你n*n个数要你构建一个每行每列都是回文的矩阵。
思路：
模拟即可。
代码实现如下：
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL; #define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-;
const int mod = ;
const int maxn = 2e5 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL; int n, x;
int mp[][], cnt[]; int main(){
scanf("%d", &n);
for(int i = ; i <= n * n; i++) {
scanf("%d", &x);
cnt[x]++;
}
if(n % == ) {
for(int i = ; i <= ; i++) {
if(cnt[i] % != ) {
return printf("NO\n") * ;
}
}
int pp = ;
for(int i = ; i <= n / ; i++) {
for(int j = ; j <= n / ; j++) {
while(cnt[pp] == ) pp++;
mp[i][j] = mp[i][n-j+] = mp[n-i+][j] = mp[n-i+][n-j+] = pp;
cnt[pp] -= ;
}
}
} else {
int num1 = , num2 = , num3 = ;
for(int i = ; i <= ; i++) {
if(cnt[i] % == ) num1++;
else if(cnt[i] % == ) num2++;
else if(cnt[i] % == ) num3++;
}
if(num2 > (n-) || (num1 > && num3 > ) || (num1 == && num3 != ) || (num3 == && num1 != )) return printf("NO\n") * ;
for(int i = ; i <= ; i++) {
if(cnt[i] % == || cnt[i] % == ) {
mp[n/+][n/+] = i;
cnt[i]--;
break;
}
}
int pp = ;
for(int i = ; i <= n / ; i++) {
for(int j = ; j <= n / ; j++) {
while(cnt[pp] < ) pp++;
mp[i][j] = mp[i][n-j+] = mp[n-i+][j] = mp[n-i+][n-j+] = pp;
cnt[pp] -= ;
}
}
pp = ;
for(int i = ; i <= n / ; i++) {
while(cnt[pp] == ) {
pp++;
if(pp > ) return printf("NO\n") * ;
}
mp[i][n/+] = mp[n-i+][n/+] = pp;
cnt[pp] -= ;
}
for(int i = ; i <= n / ; i++) {
while(cnt[pp] < ) {
pp++;
if(pp > ) return printf("NO\n") * ;
}
if(pp > ) return printf("NO\n") * ;
mp[n/+][i] = mp[n/+][n-i+] = pp;
cnt[pp] -= ;
}
}
printf("YES\n");
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
printf("%d ", mp[i][j]);
}
printf("\n");
}
return ;
}
D题：
题意：
有n杯咖啡，m页作业，每杯咖啡的权值为ai，假如你某一天喝了k杯咖啡那么你写的作业页数为a1,a2-1,a3-2……这里的1,2,3指当天喝的顺序而非原序列的下标，要你用最少的天数写完作业。
思路：
先将ai从大到小排序，二分天数，然后把所有会产生正贡献的咖啡求和，与m比较即可。
代码实现如下：
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL; #define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-;
const int mod = ;
const int maxn = 2e5 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL; int n, m;
int a[maxn]; bool check(int x) {
int tmp = ;
LL sum = ;
for(int i = ; i <= min(n, x); i++) {
sum += a[i];
}
for(int i = x + ; i <= n; i++) {
if(i % x == || x == ) tmp++;
if(a[i] - tmp > ) {
sum += a[i] - tmp;
} else {
break;
}
}
return sum >= m;
} bool cmp(int a, int b) {
return a > b;
} int main(){
scanf("%d%d", &n, &m);
LL sum = ;
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
sort(a + , a + n + , cmp);
if(sum < m) {
return printf("-1\n") * ;
}
int ub = inf, lb = , mid, ans = ;
while(ub >= lb) {
mid = (ub + lb) >> ;
if(check(mid)) {
ub = mid - ;
ans = mid;
} else {
lb = mid + ;
}
}
printf("%d\n", ans);
return ;
}
E题：
题意：
给你n和k，要你构建n对数，假设第i对为ai，bi，第j对为aj，bj，需满足一下条件：
- ai!=bi;
- ai==aj与bi==bj不能同时成立；
- 若j==i+1时，ai!=aj且bi!=bj。
思路：
第一个数一直是1~k的循环，第二个数则是2~k~1,3~k~2,4~k~2这样循环，我们知道满足题意的总排列对数只有k*(k-1)种（第一位放置方法有k种选择，第二位也有k种，故总的排列方法是k*k，其中只有1-1,2-2这种是不满足要求的），因此当n>k*(k-1)时输出NO。
代码实现如下：
#include<bits/stdc++.h>
using namespace std;
int n,k;
pair<int,int> ans[];
int main(){
scanf("%d%d",&n,&k);
if(n>1LL*k*(k-)) return puts("NO")*;
int a=,x=,y=;
for(int i = ; i<=n;i++){
ans[i]={x,y};
x++,y++;
if(x>k) x = ;
if(y>k) y =;
if(y==a) {
a++;
if(a>k) a=;
y = a;
}
}
puts("YES");
for(int i =;i<=n;i++){
printf("%d %d\n",ans[i].first,ans[i].second);
}
return ;
}
F1题：
题意：
给你一棵树，每个结点的颜色可以是0,1,2，要你删除一条边使得得到的两个联通块内不能同时出现1和2。
思路：
dfs记一下子树中的1和2的个数与总的1和2的个数比较即可。
代码实现如下：
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL; #define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-;
const int mod = ;
const int maxn = 3e5 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL; int n, u, v, num1, num2;
LL ans = ;
int a[maxn], sum1[maxn], sum2[maxn];
vector<int> G[maxn]; void dfs(int u, int p) {
if(a[u] == ) sum1[u]++;
else if(a[u] == ) sum2[u]++;
for(int i = ; i < (int)G[u].size(); i++) {
int v = G[u][i];
if(v == p) continue;
dfs(v, u);
if((sum1[v] == num1 && sum2[v] == ) || (sum2[v] == num2 && sum1[v] == )) ans++;
sum1[u] += sum1[v], sum2[u] += sum2[v];
}
} int main(){
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
if(a[i] == ) num1++;
else if(a[i] == ) num2++;
}
for(int i = ; i < n; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(, );
printf("%lld\n", ans);
return ;
}