A：炸鸡块哥哥的粉丝题
链接
题目描述
智乃作为炸鸡块哥哥的粉丝，做了一场炸鸡块哥哥的比赛后得出一个结论，那就是炸鸡块哥哥的话，最多只能信半句。
现在给你一个长度为N的字符串S，请输出前⌈N/2⌉个字符，表示只能相信半句话。
例如当炸鸡块哥哥说：“这是二分”，只能相信“这是”。
输入描述:
1
| 第一行输入一个正整数N()表示字符串长度，接下来输入一个仅包含小写英文字母的字符串SSS。
|
输出描述:
示例1
输入
复制
输出
复制
说明
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <cmath>
using namespace std;
int n;
int main()
{
double n;
cin >> n;
string s;
cin >> s;
cout << s.substr(0, ceil(n / 2.0));
return 0;
}
|
B：智乃想考一道鸽巢原理
链接
题目描述
智乃有N种不同颜色的小球，第iii种颜色的小球有ai个，放在同一个盒子中。
假设智乃每次任意取出两个不同颜色的小球并丢弃，然后重复这一过程，直到盒子为空或者只剩下一种颜色的小球。
智乃想要知道每种颜色的小球是否为最终可能被剩下的颜色。
一种小球的颜色为最终可能被剩下的颜色，当且仅当至少存在一种丢弃小球的方案使得盒子中最后只剩下（至少存在1个）该种颜色的小球。
输入描述:
1
2
3
4
5
| 第一行输入一个正整数T(1≤T≤106)
对于每组测试案例，第一行输入一个正整数N()表示有NNN种颜色的小球，接下来一行输入N个正整数ai(1≤ai≤109)表示每种颜色的小球数目。
输入数据保证∑N≤106。
|
输出描述:
1
| 输出一行NNN个整数ansi,ansi∈{0,1}，表示第i种颜色的小球是否有可能成为最终剩下的小球，如果可能输出1，否则输出0，整数之间用一个空格隔开。
|
示例1
输入
复制
输出
复制
说明
示例2
输入
复制
输出
复制
说明
1
2
| 对于第一个样例，两两相消后只会剩下第2种球。
对于第二个样例，一开始消除1,2可以剩下3；消除1,3剩下2；消除2,3剩下1。所以每种小球都可能被留到最后。
|
代码
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
| #include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define pre(i,x,y) for(int i=x; i>=y; --i)
const int N = 1e6 + 10;
int arr[N];
int pre_max[N], suff_max[N];
ll pre_sum[N];
void solve() {
int n;
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> arr[i], pre_sum[i] = pre_sum[i-1] + arr[i];
suff_max[n + 1] = 0;
for(int i = 1; i <= n; ++ i) pre_max[i] = max(pre_max[i-1], arr[i]);
for(int j = n; j >= 1; -- j) suff_max[j] = max(suff_max[j + 1], arr[j]);
for(int i = 1; i <= n; ++ i) {
ll sum = pre_sum[n], mx = max(pre_max[i-1], suff_max[i+1]);
if(mx >= sum - mx || (sum - arr[i]) & 1 && arr[i] == 1) cout << "0 ";
else cout << "1 ";
}
cout << "\n";
}
int main() {
#ifndef ONLINE_JUDGE
freopen("E:\\CLionProjects\\data.in","r",stdin);
freopen("E:\\CLionProjects\\data.out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while(t --) {
solve();
}
}
|
C：
链接
Easy version与Hard version题目中的题目要求略有区别，请注意区分，通过Hard version的代码稍加修改可通过Easy。
完全背包是一个经典问题，它指的是给你一个容量大小最大为M的背包，然后有N种物品，每种物品的体积为wi，价值为vi，且每种物品有无限多个。对于每种物品，你都可以任取若干个放入背包。
智乃现在对完全背包有了一个新的限制，假设将这N种物品放入背包后，第111种物品最终在背包内放了a1个，第2种物品最终在背包内放了a2个…，第iii种物品最终在背包内放了ai。
得到一个完全背包的答案序列[a1,a2,…,aN]。
智乃现在想要让最终的答案序列先单调非降再单调非升，且第KKK个物品在所选物品中成为选择次数最多的物品，即a1≤a2≤…≤aK≥…≥aN成立。
现在智乃将会给你这个参数K，你并不需要关注这个答案序列具体是多少，请你告诉智乃，在这个限制条件满足的前提下，智乃的背包容量分别为1,2,3,4,…,M时能够装下最大价值多少的物品。
输入描述:
1
2
3
| 第一行输入三个正整数N,M,K(1≤K≤N≤2000,1≤M≤500)表示物品的数目，背包的容量，限制条件中参数KKK的值。
接下来NNN行输入两个正整数wi,vi(1≤wi≤M,1≤vi≤106)表示物品的体积和价值。
|
输出描述:
1
| 输出一行M个非负整数，第i个数表示智乃的背包容量为i时最大能装下多少价值的物品。
|
示例1
输入
复制
输出
复制
说明
1
| 由于k=2，必须先至少取一个2号物品才能取1号物品，故在背包的容积大于9时才开始产生答案。
|
代码
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2010;
int n, m, k, w[N], v[N], tdp[N], sm[N], nm[N], ans1[N], ans2[N],dp[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
sm[i] = sm[i - 1] + w[i];
nm[i] = nm[i - 1] + v[i];
}
for (int i = 1; i <= k; i++) {
for (int j = k; j <= n; j++) {
if (sm[j] - sm[i - 1] > m) break;
tdp[sm[j] - sm[i - 1]] = max(tdp[sm[j] - sm[i - 1]], nm[j] - nm[i - 1]);
}
}
for (int _ = 1; _ <= 1; _++) {
for (int l = 1; l <= m; l++) {
for (int j = 1; j <= m; j++)
if(l <= j)dp[j] = max(dp[j - l] + tdp[l], dp[j]);
}
}
for (int i = 1; i <= m; i++) cout << dp[i] << " ";
return 0;
}
|