T1
解题思路
按照题目思路判断即可，有一些坑，后面判概率是要令总和严格大于21，并且概率要严格大于50....
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
int n,a[100005],sum;
int vis[105],tot;
int main(){
scanf ("%d",&n);
for (int i = 1;i <= n;i ++){
scanf ("%d",&a[i]);
sum += a[i];
vis[a[i]] ++;
}
if (21 - sum <= 0)
printf("DOSTA
");
else {
for (int i = 2;i <= 11;i ++){
if (i == 10){
if (21 - sum - i < 0)
tot += 16 - vis[i];
}
else if (21 - sum - i < 0)
tot += 4 - vis[i];
}
if (tot * 2 > (52 - n))
printf("DOSTA
");
else
printf("VUCI
");
}
}T2
题目描述
小时候GM很喜欢玩俄罗斯方块，游戏里有五种不同样式的方块，分别给它们编号，如下图：
现给你一个N行M列的矩阵，矩阵中.代表空白，相同相邻字母代表同一种方块。请你输出矩阵中五种方块的个数。
输入
第一行输入包含整数N，M（1≤N，M≤10）。
后面N行，每行M列，输入矩阵。
输出
五行，每行1个整数，代表对应方块的个数。
分数分布
对于20%的数据，只会出现第一种方块。
对于20%的数据，只会出现前两种方块。
对于20%的数据，只会出现前三种方块。
对于20%的数据，只会出现前四种方块。
样例输入1
4 5
aaaa.
.bb..
.bbxx
...xx
样例输出1
2
1
0
0
0
样例输入2
4 5
.aab.
aabb.
.cbaa
cccaa
样例输出2
1
0
1
1
1
样例输入3
5 7
.c.....
ccdddd.
caabbcc
aabbacc
...aaa.
样例输出3
1
1
2
1
1
解题思路
五种类型的这玩意，一共只有十二种可能，你可以枚举出所有，dfs找即可。其中发现，仅仅只有3号（1个）与5号（4个全部）有回溯，其余都是一遍搜到底。于是我们可以判断是否回溯，然后再来打表。反正我是这样做的
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,turn[105],mov1[5] = {0,1,-1,0,0},mov2[5] = {0,0,0,1,-1},tot,num[15];
char mase[15][15];
bool vis[15][15],flag;
void check(){
if (turn[1] == 1 && turn[2] == 3 && turn[3] == 2){
num[1] ++;
return ;
}
if (turn[1] == turn[2] && turn[2] == turn[3]){
num[2] ++;
return ;
}
if ((turn[1] == 1 && turn[2] == 3 && turn[3] == 1) || (turn[1] == 1 && turn[2] == 4 && turn[3] == 3)){
num[3] ++;
return ;
}
if (flag){
num[5] ++;
return ;
}
if ((turn[1] == 1 && turn[2] == 4 && turn[3] == 1) || (turn[1] == 3 && turn[2] == 1 && turn[3] == 3)){
num[4]++;
return;
}
}
void dfs(int x,int y,char c){
vis[x][y] = 1;
bool flag1 = 0;
for (int i = 1;i <= 4;i ++){
int tox = x + mov1[i];
int toy = y + mov2[i];
if (mase[tox][toy] == c && !vis[tox][toy]){
if (flag1)
flag = 1;
flag1 = 1;
turn[++ tot] = i;
dfs(tox,toy,c);
}
}
}
int main(){
//freopen("tetris.in","r",stdin);
// freopen("tetris.out","w",stdout);
scanf ("%d%d",&n,&m);
for (int i = 1;i <= n;i ++){
scanf ("
");
for (int j = 1;j <= m;j ++){
scanf ("%c",&mase[i][j]);
}
}
for (int i = 1;i <= n;i ++){
for (int j = 1;j <= m;j ++){
if (mase[i][j] != '.' && !vis[i][j]){
flag = 0;
tot = 0;
dfs(i,j,mase[i][j]);
check();
}
}
}
for (int i = 1;i <= 5;i ++)
printf("%d
",num[i]);
}T3
题目描述
如果一个用户A的密码内含有另一个用户B的密码，那么A用户就可以登录B用户的账号。问有多少对这样的用户存在，使得前者可以登录后者的账号。
输入
第一行输入包含整数N（1≤N≤20000），表示用户数量。
后面N行，每行一个字符串，表示这个用户的密码，每个串不超过10个小写字母。
输出
输出一个整数。表示满足母子密码的对数总数。
分数分布
对于40%的数据，1≤N≤2000。
样例输入1
3
aaa
aa
abb
样例输出1
1
样例输入2
3
x
x
xy
样例输出2
4
样例输入3
5
mir
mirta
ta
ir
t
样例输出3
6
解题思路
考场乱开数组，导致原地爆炸，本来AC的我顿时少了不少分。
暴力过的，时间复杂度没有问题，关键是空间（毕竟64M）。
但字符串数据并不多，并且每一个长度仅为10，空间并不会炸。
我启用map，读入一个便累加它的所有子串。嗯，很暴力。
但其中会有一些重复累加的情况，嗯，再暴力开一个map。统计即可，很舒服。
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
int n;
map<string,int>mp;
long long ans;
char s[20005][105];//f**k
string str;
int main(){
//freopen("lozinke.in","r",stdin);
// freopen("lozinke.out","w",stdout);
scanf ("%d",&n);
for (int i = 1;i <= n;i ++){
scanf ("%s",s[i]);
int len = strlen(s[i]);
str = "";
for (int j = 0;j < len;j ++)
str += s[i][j];
len = str.size();
map<string,bool>mp1;
for (int j = 0;j < len;j ++){
string str1 = "";
for (int k = j;k < len;k ++){
str1 += str[k];
if (!mp1[str1]){
mp1[str1] = 1;
mp[str1] ++;
}
}
}
}
for (int i = 1;i <= n;i ++){
int len = strlen(s[i]);
str = "";
for (int j = 0;j < len;j ++)
str += s[i][j];
if (mp[str])
ans += mp[str] - 1;
}
printf("%lld
",ans);
}T4
题目描述
冰球比赛，一队共N人(包括上场队员和替补队员)，比赛时间共M分钟，每个队员有贡献值K和耐力值I两个属性，不限制换人次数，但同一个队员不能在当前上场后同一时刻又下场(你不觉得很无聊吗)
场上队员的贡献度 = 贡献值K × 上场时间X；X可以是多段上场时间。
问教练怎么安排6名主力队员？以及什么时间谁替换谁？才能使得全场总贡献值最大。
输入
输入的第一行包含正整数M和N，比赛的时间在M分钟内,参加的队员数量N。
以下N行每行包含两个正整数，K和I，表示球员的贡献和耐力。
玩家的编号从1到N，按照输入的顺序(第一个队员的编号是1，第二个是2，以此类推)。
输出
输出的第一行必须包含来自任务的最大可能Z。
第二行输出必须包含6个数字（空格隔开），即开始游戏的6个队员的编号。
第三行输出换人次数T，不能超过3*N。
最后输出T行，每行3个数，X(1≤X < M)，A和B，其中X是替补队员加入比赛的时刻，A是退出比赛，进入板凳席的球员编号，B是将加入比赛的球员的编号。允许在同一分钟内进行多次替换。
如果存在多个解决方案，则输出任何。
分数分布
对于100%的数据：1≤I≤M≤500000，6≤N≤500000，1≤K≤100000。
样例输入1
200 6
3 200
4 200
5 200
6 200
7 200
8 200
样例输出1
6600
1 2 3 4 5 6
0
样例输入2
9 9
10 3
9 3
13 9
5 3
15 9
100 9
3 6
2 6
1 6
样例输出2
1260
1 2 3 4 5 6
3
3 1 7
3 2 8
3 4 9
样例输入3
3 9
100 3
100 3
100 3
100 3
100 2
100 1
50 1
30 2
1 1
样例输出3
1610
1 2 3 4 5 6
2
1 6 8
2 5 7
解题思路
考试当时便不会，在哪里一直试怎么排序。
正解玄学贪心，好像只有老师A了。
T5
题目描述
有一辆车上有n个小孩，年龄为1~n，然后q个询问，M X A代表在第X站时年龄为A的小孩会下车，D Y B代表询问年龄大于等于B且在第Y站（包含第Y站）以前下车的年龄最小的小孩，如果不存在，则输出-1。
输入
输入的第一行包含正整数N和Q,孩子的数量和询问的数量。
接下来Q行，每行3个值，第一个值为M或者D，询问有两种分别用M和D表示，M表示下车操作，D表示询问
如果是M X A，那么三个值的含义是：M X A代表在第X站时年龄为A的小孩会下车
如果是D Y B，代表询问年龄大于等于B且在第Y站（包含第Y站）以前下车的年龄最小的小孩，如果不存在，则输出-1。
所有询问都对应着不同的孩子，输入中至少有一行是询问的问题。
输出
对于每个询问的问题，输出答案。如果没有答案，输出-1。
分数分布
对于100%的数据：2≤N,Q≤200000，1≤X,Y≤1,000,000,000，1≤A,B≤N。
样例输入1
3 4
M 10 3
M 5 1
D 20 2
D 5 1
样例输出1
3
1
样例输入2
10 10
M 20 10
D 1 9
M 2 3
D 17 10
M 20 2
D 8 2
M 40 1
D 25 2
M 33 9
D 37 9
样例输出2
-1
-1
3
2
9
解题思路
考试还想用线段树，树状数组什么的，还打了离散化，树状数组都写好了。然而后面发现并不能（好像又可以？）。于是开始暴力。暴力的分数很震惊。感到惊异...
结果正解线段树板题。
由于年龄很小，我们用它作为线段树的下标（然后考试就没想到）。然后我们遇到查询，仅需查询B到N区间中车站是否Y，返回那个下标。最后加个剪枝：在前面区间搜到答案便不用管后面。感觉还真挺简单。其实就是改变下标这一个点。
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
struct node{
int l,r,minn;
}tree[8000005];
int n,q,cnt,a,b,ans;
char x;
void build (int i,int l,int r){
tree[i].l = l,tree[i].r = r;
tree[i].minn = 0x3f3f3f3f;
if (l == r)
return ;
int mid = (l + r) / 2;
build(i * 2,l,mid);
build (i * 2 + 1,mid + 1,r);
}
void insert(int i){
if (tree[i].r < b || tree[i].l > b)
return ;
if (tree[i].l == b && tree[i].r == b){
tree[i].minn = a;
return ;
}
insert(i * 2);
insert(i * 2 + 1);
tree[i].minn = min(tree[i * 2].minn,tree[i * 2 + 1].minn);
}
int find(int i){
if (tree[i].minn > a)
return 0x3f3f3f3f;
if (tree[i].l > n || tree[i].r < b)
return 0x3f3f3f3f;
if (tree[i].l == tree[i].r)
return tree[i].l;
int ret = 0x3f3f3f3f;
ret = min(ret,find(i * 2));
if (ret != 0x3f3f3f3f)
return ret;
else
return min(ret,find(i * 2 + 1));
}
void solve(int i){
if (b <= tree[i].l){
ans = find(i);
return ;
}
if (tree[i].r < b)
return ;
solve(i * 2);
if (ans != 0x3f3f3f3f)
return ;
solve(i * 2 + 1);
}
int main(){
scanf ("%d%d",&n,&q);
build (1,1,n);
for (int i = 1;i <= q;i ++){
scanf ("
");
scanf ("%c",&x);
scanf ("%d%d",&a,&b);
if (x == 'M')
insert(1);
else{
int ans = 0x3f3f3f3f;
ans = find(1);
printf("%d
",ans == 0x3f3f3f3f?-1:ans);
}
}
}