T1
很简单，判断这个字符串有多少个不同的字符，让后用k减一减
注意：
1、如果不同字符数大于k，不要输出负数
2、变量名别打错
上代码
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#define ll long long using namespace std; string s; inline ll read(){
ll x = 0; int zf = 1; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
} int vis[26]; int main(){
while (cin >> s){
memset(vis, 0, sizeof(vis));
int k, s_l = s.length(), cnt = 0, cnt2 = 0;
cin >> k;
if (k > s_l || k > 26)
printf("impossible\n");
else{
for (int i = 0; i < s_l; ++i){
if (s[i] < 'a' || s[i] > 'z')
continue;
if (!vis[s[i] - 'a']){
vis[s[i] - 'a'] = 1;
++cnt;
}
}
printf("%d\n", (k - cnt) < 0 ? 0 : (k - cnt));
}
}
return 0;
}
T2
我们发现可以计算组合数来解决问题
先把组合数求出来，然后我们发现，如果一行/一列有k个格子同色
相当于C1,k + C2,k + C3,k + ... + Ck,k
于是我们顺便在计算组合数的时候把上面这个序列求出来
让后问题变为求一行/一列有多少个格子颜色为0，有多少个格子颜色为一
注意单个格子也就是C1,1在行和列各被算了一次，所以要减去多算的部分即n*m
上代码：
#include <cstdio>
#include <iostream>
#define ll long long using namespace std; inline ll read(){
ll x = 0; int zf = 1; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
} unsigned ll C[102][102];
unsigned ll sum[102];
ll cac_sum[102][2]; int main(){
ll n = read(), m = read();
C[1][0] = C[1][1] = 1;
sum[0] = 0;
sum[1] = 1;
for (ll i = 2; i <= 51; ++i){
C[i][0] = 1;
sum[i] = 0;
//cout << C[i][0] << ' ';
for (ll j = 1; j < i; ++j){
C[i][j] = C[i - 1][j - 1] + C[i - 1][j], sum[i] += C[i][j];
//cout << C[i][j] << ' ';
}
C[i][i] = 1, ++sum[i];
//cout << C[i][n] << endl;
}
ll tmp, cnt[2];
unsigned ll ans = 0;
for (ll i = 0; i < n; ++i){
cnt[0] = 0, cnt[1] = 0;
for (ll j = 0; j < m; ++j){
cin >> tmp;
++cac_sum[j][tmp], ++cnt[tmp];
}
ans += sum[cnt[0]] + sum[cnt[1]];
}
for (ll i = 0; i < m; ++i)
ans += (sum[cac_sum[i][0]] + sum[cac_sum[i][1]]);
cout << (ans - (n * m));
return 0;
}
T3
思路很简单，这一列主要是判断上一列排序相同的元素是否符合排列
注意开两个数组倒来倒去(可能我比较菜)
放个代码
#include <string>
#include <cstdio>
#include <iostream>
#define ll long long using namespace std; inline ll read(){
ll x = 0; int zf = 1; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
} string s[105];
int is_not_same[105];
int is_not_same2[105]; int main(){
int n = read(), m = read();
for (int i = 0; i < n; ++i)
cin >> s[i];
int cnt = 0;
for (int i = 0; i < m; ++i){
for (int j = 1; j < n; ++j)
is_not_same2[j] = is_not_same[j];
int j;
for (j = 1; j < n; ++j){
if (!is_not_same[j]){
if (s[j - 1][i] > s[j][i]){
++cnt;
break;
}
else if (s[j - 1][i] == s[j][i])
is_not_same2[j] = 0;
else
is_not_same2[j] = 1;
}
}
if (j == n){
for (j = 1; j < n; ++j)
is_not_same[j] = is_not_same2[j];
}
}
printf("%d", cnt);
return 0;
}
T4
贪心
先排序
然后能往左倒就往左倒，不能往左倒就看可不可以往右倒
解释:
该树本身就占一格，如果不往左倒就是浪费
如果能往右倒，意味着对于后面的树来说，比下一颗树往左倒更优
解决
放个代码：
#include <cstdio>
#include <algorithm>
#define ll long long using namespace std; inline ll read(){
ll x = 0; int zf = 1; char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
} struct Tree{
int pos, hei;
} trees[100005]; int cut[100005]; bool Comp(const Tree &a, const Tree &b){
if (a.pos < b.pos)
return true;
else if (a.pos == b.pos){
if (a.hei < b.hei)
return true;
else
return false;
}
else
return false;
} int main(){
int n = read();
for (int i = 0; i < n; ++i){
trees[i].pos = read(), trees[i].hei = read();
}
sort(trees, trees + n, Comp);
int ans = 1, flg = 0;
for (int i = 1; i < n; ++i){
if (trees[i].pos - trees[i - 1].pos > trees[i].hei + (cut[i - 1] ? trees[i - 1].hei : 0)){
++ans;
} else if (((i == n - 1) ? 2147483647 : trees[i + 1].pos) - trees[i].pos > trees[i].hei){
cut[i] = 1;
++ans;
}
}
printf("%d", ans);
return 0;
}
T5
我们发现判断一个小于100的质数，只用用小于50的质数筛即可
但是，注意例如4这样的数需要特殊处理
于是如果输出一个质数的到yes，那么需要判断质数的平方
注意质数的平方如果大于100就别判了
放代码
#include <cstdio>
#include <string>
#include <iostream> using namespace std; const int p_num = 15;
int prime[20] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; int main(){
int cnt = 0;
string s;
for (int i = 0; i < p_num; ++i){
cout << prime[i] << endl;
fflush(stdout);
cin >> s;
if (s[0] == 'y'){
if ((prime[i] * prime[i]) <= 100){
cout << (prime[i] * prime[i]) << endl;
fflush(stdout);
cin >> s;
if (s[0] == 'y'){
cout << "composite" << endl;
return 0;
}
}
++cnt;
if (cnt >= 2){
cout << "composite" << endl;
return 0;
}
}
}
if (cnt == 1 || cnt == 0)
cout << "prime" << endl;
else
cout << "composite" << endl;
fflush(stdout);
return 0;
}
总结
1、据说cout自带fflush
2、5道水题，但我自闭了好几次