C001 字符串计数

Problem Description

给出m个字符串，要求输出重复n次的字符串有几个。

Input

先给定一个N，N≤100000，接着输入N个字符串。

Output

对于每组测试数据，输出若干行，每行两个正整数，第一个数表示重复的次数，第二个数表示在此重复次数下有几种不同的字符串。

Sample Input

5
BBA
BBA
BEA
DEC
CCF

Sample Output

1
2

1 3
2 1

实现思路

用map检查存每个字符的出现次数，并每输入一个就对ret数组进行动态更新，省去最后对map的遍历

实现细节

1、用map.count()来检查是否出现过

2、每进来一个，若没有则在map里加并ret[1]加1，若有则map目前存的数值对应的ret减1，下一个加1

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
string s;
int ret[100010];
map<string,int> a;
int main()
{
    int n,tem;
    while (cin >> n)
    {
        memset(ret,0,sizeof(ret));
        for (int i=1;i<=n;i++)
        {
            cin >> s;
            if (a.count(s)==0)
            {
                a[s] = 1;
                ret[1]++;
            }
            else
            {
                tem = ++a[s];
                ret[tem-1]--;
                ret[tem]++;
            }
        }
        int co=0;
        for (int i=1;;i++)
        {
            if (ret[i]!=0)
            {
                cout << i << " " << ret[i] << endl;
                co+=i*ret[i];
            }
            if (n==co) break;
        }
    }
}

C002 赌徒（Gamblers）

Problem Description

N个赌徒一起决定玩一个游戏：
游戏刚开始的时候，每个赌徒把赌注放在桌上并遮住，侍者要查看每个人的赌注并确保每个人的赌注都不一样。如果一个赌徒没钱了，则他要借一些筹码，因此他的赌注为负数。假定赌注都是整数。
最后赌徒们揭开盖子，出示他们的赌注。如果谁下的赌注是其他赌徒中某3个人下的赌注之和，则他是胜利者。如果有多于一个胜利者，则下的赌注最大的赌徒才是最终的胜利者。
例如，假定赌徒为：Tom、Bill、John、Roger和Bush，他们下的赌注分别为：$2、$3、$5、$7和$12 。因此最终获胜的是Bush（并且没有其他人是胜利者），因为他下的赌注为$12，而其他的人下的赌注之和也等于12：2+2+3+7=7=12。

Input

输入文件中包含了多组赌徒下的赌注。每组赌注的数据第1行是一个整数n,1<=n<=1000,代表赌徒的个数，然后是他们下的赌注，每个人的赌注占一行，这些赌注各不相同，并且范围是[-536870912,+536870911]。输入文件的最后一行为0，代表输入结束。

Output

对每组赌注，输出胜利者下的赌注，如果没有解，则输出“no solution”。

Sample Input

Sample Output

1 2	12 no solution

实现思路

用一个暴力n三次log的算法，最后找和的时候用二分

实现细节

1、当n<=3时要输出no solution，但是这里要等输完那几个赌注后在判断

2、由于会出现负数，所以对一个有序序列穷举三个数后，和的数有可能出现在除了他们三个的任何位置，所以这里使用了分段bs

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int a[1010];
bool bs(int be,int end,ll v)
{
    if (be>end)
        return false;
    int mid = (be+end)/2;
    if (a[mid] == v)
        return true;
    if (a[mid]>v)
        return bs(be, mid-1, v);
    else return bs(mid+1, end, v);
}
int main()
{
    int n;
    while (cin >> n)
    {
        if (n==0) break;
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        if (n<=3)
        {
            cout << "no solution" << endl;
            continue;
        }
        sort(a+1,a+n+1);
        int ret = -INF;
        for (int i=1;i<=n-2;i++)
            for (int j=i+1;j<=n-1;j++)
                for (int k=j+1;k<=n;k++)
                {
                    if (bs(1, n-1, a[i]+a[j]+a[k]))
                        ret = max(ret,a[i]+a[j]+a[k]);
                    if (bs(i+1, j-1, a[i]+a[j]+a[k]))
                        ret = max(ret,a[i]+a[j]+a[k]);
                    if (bs(j+1, k-1, a[i]+a[j]+a[k]))
                        ret = max(ret,a[i]+a[j]+a[k]);
                    if (bs(k+1, n, a[i]+a[j]+a[k]))
                        ret = max(ret,a[i]+a[j]+a[k]);
                }
        if (ret!=-INF)
            cout << ret << endl;
        else cout << "no solution" << endl;
    }
}

C003 半素数（Semi-Prime）

Problem Description

素数的定义：对于一个大于１的正整数，如果除了１和它本身没有其他的正约数了，那么这个数就称为素数。例如，2,11,67,89是素数，8,20,27不是素数。
半素数的定义：对于一个大于1的正整数，如果它可以被分解成2个素数的乘积，则称该数为半素数，例如6是一个半素数，而12不是。
你的任务是判断一个数是否是半素数。

Input

输入文件中有多个测试数据，每个测试数据包含一个整数N，2<=N<=1,000,000。

Output

对每个测试数据，如果N是半素数，则输出YES，否则输出NO。

Sample Input

Sample Output

No
Yes
Yes
No

实现思路

先打个素数表，然后利用prim数组和is数组判断能拆分的两个数是否均为素数

实现细节

1、在筛选素数时，把每个素数的所有倍数均置一，然后挪动到下一个素数，重复上述操作

2、这里不需要用到二分

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
int a[1010];
bool bs(int be,int end,ll v)
{
    if (be>end)
        return false;
    int mid = (be+end)/2;
    if (a[mid] == v)
        return true;
    if (a[mid]>v)
        return bs(be, mid-1, v);
    else return bs(mid+1, end, v);
}
bool is[500010];
int pri[300010];
int getprim()
{
    memset(is,1,sizeof(is));
    is[0]=is[1]=0;
    for (int i=2;i<=500000;)
    {
        for (int j = i*2;j<=500000;j+=i)
            is[j]=0;
        i++;
        while (!is[i]) i++;
    }
    int co=0;
    for (int i=2;i<=500000;i++)
    {
        if (is[i])
            pri[++co] = i;
    }
    return co;
}
int main()
{
    int n,num;
    num = getprim();
    while (cin >> n)
    {
        bool flag = false;
        for (int i=1;i<=num;i++)
        {
            if (n % pri[i]!=0)
                continue;
            if (is[n/pri[i]])
            {
                flag = true;
                cout << "Yes" << endl;
                break;
            }
        }
        if (!flag)
            cout <<"No" << endl;
    }
}

C004 棍子的膨胀（Expanding Rods）

Problem Description

当一根长度为L的细长金属棍子加热n度后，它会膨胀到一个新的长度L’=(1+nC)L,其中C为该金属的热膨胀系数。
当一根细长的金属棍子固定在两堵墙之间，然后加热，则棍子会变成圆弓形，棍子的原始位置为该圆弓形的弦，如图所示。

图膨胀的金属棍子（上为膨胀前，下为膨胀后）
你的任务是计算棍子中心的偏离距离。

Input

输入文件包含多个测试数据，每个测试数据占一行。每个测试数据包含3个非负整数：棍子的初始长度，单位为毫米；加热前后的温差，单位为度；该金属的热膨胀系数。输入数据保证膨胀的长度不超过棍子本身长度的一半。输入文件的最后一行为3个负数，代表输入结束，该测试数据不需处理。

Output

对每个测试数据，输出金属棍子中心加热后偏离的距离，单位为毫米，保留小数点后3位有效数字。

Sample Input

1000 100 0.0001
15000 10 0.00006
10 0 0.001
-1 -1 -1

Sample Output

1
2
3

61.329
225.020
0.000

实现思路

这。。。题目过于奇怪。思路似乎十分简单，就是简单的二分法解方程罢了，可是这个最后的这个精度控制却极其诡异。

实现细节

1、这里阐述一下思路：这里二分求角度，利用三角关系求出弧长，然后二分逼近弧长即可

2、这里有个奇怪的点在于不能用递归二分？？我也不知道为什么

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
double leng;
    double a,b,c;
const double pi = acos(-1.0);
int main()
{
    while (cin >> a >> b >> c)
    {
        if (a<0 && b<0 && c<0)
            break;
        if(a<= 1e-6 || b<=1e-6 || c<=1e-6)
        {
            printf("0.000\n");
            continue;
        }

        leng = (1.0+b*c)*(double)a;
        a*=0.5;
        double le = 0;
        double ri = pi;
        double mid;
        double temp;
        while (fabs(le-ri)>1e-6)
        {
            mid = (le+ri)/2.0;
            temp = mid*a/sin(0.5*mid);
            if (temp<=leng)
                le = mid;
            else ri = mid;
        }
        printf("%.3lf\n",a*tan(mid*0.25));
    }
}

C006 宝贝鱼（Babelfish）

Problem Description

你刚刚从奶牛搬到一个大城市里。这里的人说一种让人理解不能的外文方言。万幸，你有本字典可以帮助你理解。

Input

输入包含多达100，000个字典词条，然后是一个空行，然后是一条消息，这条消息包含多达100，000个单词。每个词条占一行，先是一个英语单词，然后是一个空格，然后是一个外文方言词。一个方言词在字典中出现不超过一次。消息是一个外文方言词序列，一个词占一行。每个词是一个最长为10的小写字母序列。

Output

将消息的外文词翻译成英语，一个词一行。查不到的词应该翻译成“eh”。

Sample Input

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

Sample Output

1
2
3

cat
eh
loops

实现思路

这道题的难点在于输入问题，其他就是暴力建立字典然后暴力查找就可

实现细节

1、由于存在读取换行符的问题，这里必须使用逐字符读取的方式，如果读到的字符只有\n，那么说明是个换行，跳出读取部分

2、那么如此在读取真实的字典内容时，现逐字符读取第一个单词，知道空格停止，对于下一个字符直接用gets读取整行，防止本行字符对下面的读取造成影响。

3、下面在读入的时候要使用gets()!=NULL

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
char a[10001];
struct line{
    char word[20];
    char trans[20];
}str[1000001];

int main(){
    int i=0,j=0,n=0;
    char b[22];
    memset(str,0,sizeof(str[0]));
    while(~scanf("%c",&str[i].word[j])){
        while(str[i].word[j]!='\n'&&str[i].word[j]!=' '){
            j++;
            scanf("%c",&str[i].word[j]);
        }
        if(str[i].word[j]=='\n')
            break;
        str[i].word[j]='\0';
        gets(str[i].trans);
        i++;
        j=0;
    }
    n=i;
    while(gets(b)!=NULL){
        for(i=0;i<n;i++){
            if(strcmp(b,str[i].trans)==0){
                printf("%s\n",str[i].word);
                break;
            }
        }
        if(i>=n)
            printf("eh\n");
    }
}

C007 星空（Squares）

Problem Description

将夜空抽象成二维平面，每个星星一个(X,Y)坐标。这些点可以形成多少正方形？

Input

多组输入。对于每组数据，第一行是n（1<=n<=1000）表示已知星星数，然后是n行，每行一个坐标值。坐标绝对值小于20000。n=0表示结束。

Output

对于每组数据输出形成正方形的个数。

Sample Input

Sample Output

1
2
3

1
6
1

实现思路

这里要注意正方形可以时斜的，第一遍的时候写错了。那么就先按x坐标小到大排序，然后先不重复地遍历前两个点，然后查找后两个点是否存在即可

实现细节

这里主要是要使查找的时候不要重复。我这里选取的策略是选取往右上方翘的边作为主边，然后再把竖着的边也删去即可。

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
struct star
{
    int x;
    int y;
};
star a[1010];
bool cmp(star p1,star p2)
{
    return p1.x<p2.x;
}
int main()
{
    int n;
    while (cin >> n)
    {
        if(n==0)
            break;
        for (int i=1;i<=n;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        sort(a+1,a+n+1,cmp);
        int ret =0,decx,decy;
        bool flag;
        star f1,f2;
        for (int i=1;i<=n;i++)
            for (int j=i+1;j<=n;j++)
            {
                if (a[j].y<a[i].y || a[j].x == a[i].x)
                    continue;
                decx = a[j].x-a[i].x;
                f1.y = a[i].y-decx;
                decy = a[j].y-a[i].y;
                f1.x = a[i].x+decy;
                f2.y = f1.y+decy;
                f2.x = f1.x+decx;
                flag = false;
                for (int k=1;k<=n;k++)
                {
                    if (a[k].x == f1.x && a[k].y==f1.y)
                        flag= true;
                    if (flag && a[k].x == f2.x && a[k].y==f2.y)
                    {
                        ret++;
                        break;
                    }
                }
            }
        cout << ret << endl;
    }
}