这次校赛就目的而言,是为第六届山东省赛做准备的。主要是为了测试服务器压力。

说说做题状况,刚开始四道水题,都是一遍过,很顺利,做完后就成了冠军。然后开始做那个IP判断的题,由于出题出的实在是太不清晰了(实在不是我的个人原因,比完赛题目重现时题目完善后篇幅增加了一倍,敲完一遍过),重写了5遍,交了15遍也没有过,像这种水题,前30名只有我一个人没过,是相当的难受的,是对心理的巨大考验。但我还是没有承受这么大的心理压力,导致三个小时内没有出题,没有心思看其他题,一直掉到铁牌去。直到最后封榜,才逐渐稳定下来,做出一道搜索题。直到最后比赛,一共做出来五道题,只拿了铜牌,实在是遗憾+伤心。当然也有我的原因,还是太水,还是不够镇定。

 

 

 

 

Problem A: 简单计算

 

 

 

 

Description

给出n个十进制的数,找出这n个数的二进制表示中1的个数最少的数。

 

Input

输入的第一行为一个正整数T(1≤T≤20),代表测试数据组数。
对于每组测试数据,输入的第一行为一个正整数n(1≤n≤100000),第二行为n个正整数A1、A2、…、An(1≤Ai≤10^9),每个数之间以空格分隔。

 

Output

每组数据输出一行,先输出数据组数,再输出二进制中含1最少的数,如果存在多个数符合条件,输出最小的那个。具体输出格式见样例输出。

 

Sample Input

2 5 3 2 4 5 6 4 3 4 2 5

Sample Output

Case 1: 2
Case 2: 2

水题一个,STL依赖症患者,直接上bitset

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int T, kase = 0; cin >> T;
    while(T--){
        int n; cin >> n;
        int min1 = INT_MAX, minn = INT_MAX;
        for(int i = 0; i < n; ++i){
            int t; cin >> t;
            bitset<100> bit(t);
            if(bit.count() < min1 || (bit.count() == min1 && t < minn)){
                min1 = bit.count();
                minn = t;
            }
        }
        printf("Case %d: %d\n", ++kase, minn);
    }
    return 0;
}

 

 

 

 

 

Problem C: 正方形

 

 

 

 

Description

在二维坐标轴内给出四个点,这四个点能否构成一个正方形。

 

Input

第一行包括一个整数:T(1≤T≤30),表明有T组测试数据。
下面各行有8个整数:x1,y1,x2,y2,x3,y3,x4,y4(数据均在-1000,1000之间),以逆时针顺序给出四个点的坐标。

 

Output

对每个样例,如果是正方形,则单独在一行内输出YES,否则,输出NO。

 

Sample Input

2
0 0
1 0
1 1
0 1
-1 0
0 -2
1 0
2 0

Sample Output

YES
NO

几何简单题,还是用向量比较方便,注意数据类型用int即可,如果用double可能会有精度问题。

#include <bits/stdc++.h>
using namespace std;
 
struct Vec{
    int a, b;
    Vec(int a = 0, int b = 0):a(a), b(b){}
    Vec operator - (const Vec & rhs) const {
        return Vec(a - rhs.a, b - rhs.b);
    }
    int len() {return hypot(a, b);}
    int operator * (const Vec & rhs) const {
        return a * rhs.a + b * rhs.b;
    }
};
 
inline bool isEqual(int a, int b){
    return fabs(a-b)==0;
}
 
int main()
{
    int T; cin >> T;
    while(T--){
        Vec p[4], v[4];
        for(int i = 0; i < 4; ++i)
            cin >> p[i].a >> p[i].b;
        for(int i = 0; i < 4; ++i)
            v[i] = p[(i+1)%4] - p[i];
        bool ok = true;
        int len = v[0].len();
        for(int i = 0; i < 4; ++i)
            if(!isEqual(v[i] * v[(i+1)%4], 0) || !isEqual(len, v[i].len()))
                ok = false;
        if(!ok) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}
 

 

 

 

 

Problem D: 切蛋糕

 

 

 

 

Description

今年是ACM集训队成立五周年,这是一个值得祝福的事情。我们该送给ACM集训队一个怎样的礼物呢?对于目前的大家来说,最好的礼物当然是省赛中的好成绩,我不能参赛,就送给学校一个DOOM III球形大蛋糕吧,这可是名牌,估计要花掉我半年的银子呢。切蛋糕的人,当然非吴教主莫属。
等一等,吃蛋糕之前先考大家一个问题:如果吴教主在蛋糕上切了N刀(教主刀法极好,每一刀都是一个绝对的平面),最多可以把这个球形蛋糕切成几块呢?
做不出这个题目,没有蛋糕吃的!

 

Input

第一行输出一个T(T≤100),表示有T组。每组包含一个整数N(1≤N≤1000),表示切的刀数。

 

Output

对于每组输入数据,请输出对应的蛋糕块数,每个测试实例输出一行。

 

Sample Input

3
1
2
4

Sample Output

2
4
15

 一看就是递推,找规律(确实,规律我是才出来的,没有证明)

#include <bits/stdc++.h>
using namespace std;
 
int d[1024], res[1024];
 
void init(){
    d[1] = 2;
    for(int i = 2; i < 1024; ++i)
        d[i] = d[i-1] + i;
    res[1] = 2;
    for(int i = 2; i < 1005; ++i)
        res[i] = res[i-1] + d[i-1];
}
 
int main()
{
    init();
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        cout << res[n] << endl;
    }
    return 0;
}

 

 

 

 

Problem E: 画笑脸

 

 

 

 

Description

用C语言画些任意大小的笑脸来。画法见Sample。

 

Input

T组数据,每组数据只有一个数N(1≤T≤20,1≤N≤20),表示笑脸的边长大小。

 

Output

把笑脸画出来吧。
注意:不要任何多余的空格和空行,每两组数据间输出一个空行。

 

Sample Input

3
1
2
3

简单题, 找到了当年做C语言题的感觉。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(j == n-i-1) printf("/");
                else printf(" ");
            }
            for(int j = 0; j < n; ++j){
                if(j == i) printf("\\");
                else printf(" ");
            }
            for(int j = 0; j < n; ++j)
                printf(" ");
            for(int j = 0; j < n; ++j){
                if(j == n-i-1) printf("/");
                else printf(" ");
            }
            for(int j = 0; j < n; ++j){
                if(j == i) printf("\\");
                else if(j < i)printf(" ");
            }
            printf("\n");
        }
        for(int i = 0; i < n-1; ++i)
            printf("\n");
        for(int i = 0; i < 2*n; ++i)
            printf(" ");
        for(int i = 0; i < n; ++i)
            printf("_");
        printf("\n");
        if(T) printf("\n");
    }
    return 0;
}

 

 

 

 

Problem F: 猜数字

 

 

 

 

Description

小X最近发明了一种新游戏,他找来一堆卡片,每张卡片上都写有一个四位数,然后由两个人来玩。玩家A每次从这堆卡片中选择一张,然后由玩家B告诉玩家A他猜的数字中有几个与卡片中的相同,有几个与卡片中的位置相同。

例如,玩家A抽到的卡片是1122。如果玩家A猜1234,因为1,2这两个数字同时存在于这两个数中,而且1在这两个数中的位置是相同的,所以玩家B会告诉玩家A猜对了2个数字,其中一个在正确的位置。如果玩家A猜1111,那么玩家B会告诉他猜对2个数字,有2个在正确的位置。

现在给你一段游戏过程,你的任务是根据这过程来判断能否确定卡片上的四位数是什么。

 

Input

输入数据有多组。每组的第一行为一个正整数N(1≤N≤100),表示共有N次游戏过程。在接下来的N行中,每行三个整数x, y, z。玩家A猜这个四位数为x,然后玩家B回答猜对了y个数字,其中z个在正确的位置上。当N=0时,输入数据结束。

 

Output

每组输入数据对应一行输出。如果根据这段对话能确定这个四位数,则输出”Yes”,若不能,则输出"Not sure"。

 

Sample Input

6
4815 2 1
5716 1 0
7842 1 0
4901 0 0
8585 3 3
8555 3 2
2
4815 0 0
2999 3 3 0

Sample Output

Yes
Not sure

直接暴力枚举即可,还算简单

#include <bits/stdc++.h>
using namespace std;
 
int haveDigit(int a, int b){
    int cnt[10], res = 0; memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < 4; ++i)
        ++cnt[a%10], a /= 10;
    for(int i = 0; i < 4; ++i){
        if(cnt[b%10]) ++res, --cnt[b%10];
        b /= 10;
    }
    return res;
}
 
int samePos(int a, int b){
    int cnt = 0;
    for(int i = 0; i < 4; ++i){
        if(a%10 == b%10) ++cnt;
        a /= 10; b /= 10;
    }
    return cnt;
}
 
int main()
{
    int n;
    while(cin >> n, n){
        int cai[128][3];
        for(int i = 0; i < n; ++i)
            cin >> cai[i][0] >> cai[i][1] >> cai[i][2];
        int cnt = 0;
        for(int i = 0; i <= 9999; ++i){
            bool ok = true;
            for(int j = 0; j < n; ++j){
                if(!(haveDigit(i, cai[j][0])==cai[j][1]) || !(samePos(i, cai[j][0])==cai[j][2])){
                    ok = false;
                    break;
                }
            }
            if(ok) ++cnt;
            if(cnt > 1) break;
        }
        if(cnt == 1) puts("Yes");
        else puts("Not sure");
    }
    return 0;
}

 

 

 

 

Problem G: 排火柴

 

 

 

 

Description

小X有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为: ,其中ai表示第一列火柴中第i个火柴的高度,bi表示第二列火柴中第i个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。

 

Input

多组测试数据。第一行输入一个数T(T≤20),表示测试数据组数。
对于每组测试数据输入共三行。
第一行包含一个整数 n,表示每盒中火柴的数目。
第二行有n个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。
第三行有n个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。
数据范围:1≤n≤100,000,0≤火柴高度≤231-1。

 

Output

每组测试数据输出一行,每行包含一个整数,表示最少交换次数对99,999,997取模的结果。

 

Sample Input

2
4
2 3 1 4
3 2 1 4
4
1 3 4 2
1 7 2 4

Sample Output

1
2

 归并排序求逆序对数,貌似是一年的noip题目。

#include <bits/stdc++.h>
using namespace std;
 
struct One{
    int len, pos;
    bool operator < (const One & rhs) const {
        return len < rhs.len;
    }
};
 
const int mod = 99999997;
const int maxn = 102400;
One a[maxn], b[maxn];
int c[maxn], t[maxn], cnt;
 
void mergeSort(int x, int y){
    if(y - x > 1){
        int m = x + (y-x) / 2;
        int p = x, q = m, i = x;
        mergeSort(x, m);
        mergeSort(m, y);
        while(p < m || q < y){
            if(q >= y || (p < m && c[p] <= c[q]))
                t[i++] = c[p++];
            else t[i++] = c[q++], cnt = (cnt + m - p) % mod;
        }
        for(i = x; i < y; ++i) c[i] = t[i];
    }
}
 
int main()
{
    //freopen("in", "r", stdin);
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        for(int i = 0; i < n; ++i)
            cin >> a[i].len, a[i].pos = i;
        for(int i = 0; i < n; ++i)
            cin >> b[i].len, b[i].pos = i;
        sort(a, a + n); sort(b, b + n);
        for(int i = 0; i < n; ++i)
            c[a[i].pos] = b[i].pos;
        cnt = 0;
        mergeSort(0, n);
        cout << cnt << endl;
    }
    return 0;
}

 

 

 

 

Problem H: 原创字符串

 

 

 

 

Description

我们称一个字符串s为“原创”当且仅当s不是N个字符串中的任意一个字符串的子串(子串:串中任意个连续字符组成的子序列)。现在有N个只包含小写字母的字符串,你的任务是根据给出的N个字符串构造一个长度最小的“原创”字符串,如果存在多个长度最小的则输出字典序最小的那个。

 

Input

对于每组测试数据,输入的第一行为一个正整数n(1≤n≤30)代表给定字符串的大小,接下来N行每行一个非空只包含小写字母的字符串,每个字符串长度不超过20。
输入以一行0结束。

 

Output

输出符合要求的字符串,每组答案占一行。

 

Sample Input

5
threehorses
goodsubstrings
secret
primematrix
beautifulyear
4
aa
bdefghijklmn
opqrstuvwxyz
c
0

Sample Output

j
ab

 挺好的一道题,用set保存,用BFS搜索查询

#include <bits/stdc++.h>
using namespace std;
 
set<string> s;
 
int main()
{
    int n;
    while(s.clear(), cin >> n, cin.get(), n){
        while(n--){
            string str; cin >> str;
            for(unsigned i = 0; i < str.size(); ++i)
                for(unsigned j = i + 1; j <= str.size(); ++j)
                    s.insert(str.substr(i, j - i));
        }
        queue<string> qu;
        for(int i = 0; i < 26; ++i)
            qu.push(string().append(1, 'a'+i));
        while(true){
            string cur = qu.front(); qu.pop();
            if(!s.count(cur)){
                cout << cur << endl;
                break;
            }
            for(int i = 0; i < 26; ++i)
                qu.push(cur + char('a'+i));
        }
    }
    return 0;
}

 

 

 

 

Problem I: IP地址

 

 

 

 

Description

 

IP是英文Internet Protocol的缩写,意思是“网络之间互连的协议”,也就是为计算机网络相互连接进行通信而设计的协议。在因特网中,它是能使连接到网上的所有计算机网络实现相互通信的一套规则,规定了计算机在因特网上进行通信时应当遵守的规则。任何厂家生产的计算机系统,只要遵守IP协议就可以与因特网互连互通。正是因为有了IP协议,因特网才得以迅速发展成为世界上最大的、开放的计算机通信网络。因此,IP协议也可以叫做“因特网协议”。

互联网协议地址(英语:Internet Protocol Address,又译为网际协议地址),缩写为IP地址(IP Address),在Internet上,一种给主机编址的方式。常见的IP地址,分为IPv4与IPv6两大类。

IP地址被用来给Internet上的电脑一个编号。大家日常见到的情况是每台联网的PC上都需要有IP地址,才能正常通信。我们可以把“个人电脑”比作“一台电话”,那么“IP地址”就相当于“电话号码”,而Internet中的路由器,就相当于电信局的“程控式交换机”。

IP地址是一个32位的二进制数,通常被分割为4个“8位二进制数”(也就是4个字节)。IP地址通常用“点分十进制”表示成(a.b.c.d)的形式,其中,a,b,c,d都是0~255之间的十进制整数。例:点分十进IP地址(100.4.5.6),实际上是32位二进制数(01100100.00000100.00000101.00000110)。

现在,根据以下规则,编写程序来判断一个字符串是否是“点分十进制”表示的IP地址。

1 IP地址由四个整数跟三个'.'组成,就是“a.b.c.d”的形式。

2 a,b,c,d四个部分的数字位数都可以是1~3位,其整数值都在0~255之间。

3 不能有除了数字和'.'之外的字符出现。

 

 

Input

输入有多行,每行是一个字符串s,s不超过100个字符。到文件尾结束。

 

Output

对于每个输入,判断串s是否为合法的IP地址,如果正确输出YES,否则NO。

 

Sample Input

192.168.100.16

Sample Output

YES

 看现在的题目表述多么清晰,真是气死人了,比赛也不说清楚,水题一道!

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    char ip[1000];
    while(gets(ip)){
        int len = strlen(ip);
        int dotCnt(0), num(0), cnt(0);
        bool ok = true;
        for(int i = 0; i <= len; ++i){
            if(!isdigit(ip[i]) && ip[i]!=0 && ip[i]!='.'){
                ok = false;
                break;
            }
            if(ip[i]=='.' || ip[i]==0){
                ++dotCnt;
                if(cnt > 3 || cnt < 1 || num > 255 || num < 0){
                    ok = false;
                    break;
                }
                num = 0; cnt = 0;
            }
            else num = num * 10 + ip[i] - '0', ++cnt;
        }
        if(dotCnt==4 && ok) puts("YES");
        else puts("NO");
    }
    return 0;
}

 

 

 

 

Problem K: 藏头诗

 

 

 

 

Description

ACM集训队有个小伙暗恋同班的姑娘,但是苦于害羞腼腆不敢直抒胸臆。于是小伙打算写一首英文情诗给她。为了使这首情诗高端霸气上档次,小伙经过三天三夜的精心创作写了一首藏头的情诗。请问你能看出他想要表达的真正内容吗?

 

Input

输入有T组(T≤20)。
每组数据第一行先输入一个整数N(N<100),表示下面要输入N行。
接下来N行,每行输入一段英文(长度小于100,只含大小写英文字母和空格)。

 

Output

每组输出一行,为藏头诗要表达的真正内容。

 

Sample Input

1
8
I am a handsome man
lonely and long for you attention
of all the girls I met you gave me the deepest impression
Very lucky to know you
earn money to make you happy
you are the world
oh be ma side
u are the happiest person in the world

Sample Output

IloVeyou

水题,不解释了,好做

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int T; cin >> T;
    while(T--){
        int n; cin >> n; cin.get();
        string res, str;
        while(n--){
            getline(cin, str);
            res += str[0];
        }
        cout << res << endl;
    }
    return 0;
}

 

欢迎留言