计院实训——USACO Section 1

假期感觉自己基础还不太扎实就顺便做了下计院实训USACO题组~
所有Section 1里的题目会在本篇里陆续更新。题目源为洛谷，不过和实训内容应该是基本一致的。

P1201 [USACO1.1]你的飞碟在这儿Your Ride Is Here

没啥好说的，入门难度题。注意到’A’的ASCII码为65，故对字符串里的每个字符减去64就是其对应的数字，乘起来完事。每一次乘都取47的模，防止爆int(貌似不取也不会爆？)。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
	char h[7],u[7];
	int hm=1,um=1,i;
	cin>>h;
	cin>>u;
	int lenh=strlen(h);
	int lenu=strlen(u);
	for(i=0;i<lenh;i++){
		hm*=h[i]-64;
		}
		hm%=47;
	for(i=0;i<lenu;i++){
		um*=u[i]-64;
		}
		um%=47;
		if(um==hm){cout<<"GO";}
		else{cout<<"STAY";}
		return 0;
	}

P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers

这道题建议使用STL里的map，程序简洁度和速度都会提高一些。不会的可以取百度，反正之后数据结构里也要学。先读入名字存入map，钱数默认为0。然后再读入送礼人和礼金，将礼金平均加到收礼人账上，最后再在送礼人账上减去实际送出的礼金（25/6=4，但4*6=24，实际要退回一块钱的这种情况）。最后输出每个人账上的钱数即可。

Code

#include<cstdio>
#include<iostream>
#include<map>
#include<string>
using namespace std;

int main(){
    map<string,int> giver;
    int n;
    string k[10];
    cin >> n;
    for (int i = 0; i < n;i++){
        string z;
        cin >> z;
        k[i]=z;
        giver.insert(make_pair(z,0)); //insert插入map时要求以pair形式
    }
    for (int i = 0; i < n;i++){
        int rec,money;
        string z;
        cin >> z;   //读入送礼人名字
        cin >> money >> rec;    //读入礼金和收礼人数量
        for (int j = 0; j < rec;j++){   //均分礼金记账
            string t;
            cin >> t;
            giver[t] += money / rec;
        }
        if(rec){        //如果收礼人不为0的话，减去实际送出的礼金（如果不加可能会有分母为0的情况导致错误）
        giver[z] -= (money/rec)*rec;
        } 
        else{   //否则直接返还所有礼金
            giver[z] += money;
        }
    }
    for (int i=0;i<n;i++){
        cout << k[i]<<" "<<giver[k[i]]<< "\n";
    }
    return 0;
}

P1202 [USACO1.1]黑色星期五Friday the Thirteenth

还在打又长又容易逻辑错误的模拟？这边建议了解下基姆拉尔森计算公式或蔡勒公式。利用它们可以很快的算出每月的十三号是星期几。不过我想这种超长公式也不会有人记的，平常可以用用。常规思路是通过这月十三号是星期几推导出下个月十三号是星期几，而非一天天遍历过去。下面给出公式写法。

Code

#include<cstdio>
#include<iostream>
using namespace std;

int main(){
    int n;
    int day[8] = {0};
    cin >> n;
    for (int i = 1900; i < 1900 + n;i++){
        for (int j = 1; j <= 12;j++){
            if(j==1||j==2){
                j += 12;
                i--;
                day[(13 + 2 * j + 3 * (j + 1) / 5 + i + i / 4 - i / 100 + i / 400 + 1) % 7]++;
                i++;
                j -= 12;
            }
            else{
                day[(13 + 2 * j + 3 * (j + 1) / 5 + i + i / 4 - i / 100 + i / 400 + 1) % 7]++;
            }
        }
    }
    cout << day[6] << " " << day[0] << " ";
    for (int i = 1; i < 6;i++){
        cout << day[i] << " ";
    }
}

嗯，贴公式写法是因为懒得打模拟了（逃

P1203 [USACO1.1]坏掉的项链Broken Necklace

正解应该是动态规划。不过350的数据范围？上暴力吧。把项链复制成两倍长就可以当成环遍历了。差不多就是对每个字符左边扫一遍右边扫一遍算出连续相同的珠子加起来，只要存下可收集珠子的最大值就行了。

Code

#include<cstdio>
#include<iostream>
using namespace std;

int main(){
    char lace[800];
    int n, ans=0;
    cin >> n;
    cin >> lace;
    for (int i = 0; i < n - 1; i++){ //复制链，变为环方便遍历
        lace[n + i] = lace[i];
    }
    lace[n * 2 - 1] = '\0';
    for (int i = 0; i < n;i++){
        int l = 1, r = 1;   //设置左右连续数初始值（也可以作为判定起点)
        char judge = lace[i];   //以当前珠子为判断连续标准
        while (judge == 'w' && l < n){  //如果当前珠子为白色，且连续数不超过总长
            judge = lace[i + l];        //珠子颜色为下一颗珠子的颜色
            l++;                        //连续数++
        }
        while((lace[i+l]==judge||lace[i+l]=='w')&&l<n){//当珠子为白珠子或与judge颜色相同,且连续数不超过总长时
            l++;        //连续数++
        }
        judge = lace[n + i - 1]; //在当前珠子的向右一颗珠子为起点/标准开始向左扫描连续数（这里是复制后的珠子的位置，从这向左扫不用担心扫描到链的尽头（好像多此一举，反正都要判断一次。。））
        if(l<n){//如果右连续数还没大于总长，就向左扫
        r++;    //从当前珠子的左边第二个开始比，因为判断标准是左边第一颗珠子，相当于是在当前珠子和它左边珠子的中间断开项链。
        while (judge == 'w' && r - 1 < n - l)//和左扫逻辑一致。
            {
                judge = lace[n + i - r];
                r++;
        }
        while ((lace[n+i-r]==judge||lace[n+i-r]=='w')&&r-1<n-l)
        {
            r++;
        }
        } 
        ans = max(ans, r + l - 1);//减去多算的一个连续数。
    }
    cout << ans;
    return 0;
}

我之前写的时候思路也不是很清晰。。所以注释尽量写详细了。。可能还是有点绕吧，大概就是这么个思路就是了（暗示烂代码看不懂很正常)

P3864 [USACO1.2]命名那个数字 Name That Number

肯定不能通过数字枚举可能的字母组合再去查就是了，因为这样最多可能有3的12次方种可能…
不过字典里只有4671行，用字典里的匹配数字的时间是可以接受的！建立一个字符到数字的映射，检索每一个有效名字的映射是否符合数字就OK。下面是洛谷数据的写法（洛谷的字典是标准输入的，PTA上就不清楚啦)

Code

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

char key[26] = {'2', '2', '2', '3', '3', '3', '4', '4', '4', '5', '5', '5', '6', '6', '6', '7', '0', '7', '7', '8', '8', '8', '9', '9', '9', '0'};      //映射建立
int main(){
    char c[15], z[15];
    int ans = 0;
    cin >> c;
    while (cin >> z)
    {
        if(strlen(z)!=strlen(c)){ //长度不等直接跳过，肯定无法匹配
            continue;
        }
        else{
            int f = 1;
            for (int i = 0; i < strlen(c);i++){ //映射逐个匹配
                if(key[z[i]-'A']!=c[i]){
                    f = 0;      //标记不匹配
                    break;
                }
            }
            if(f){  //如果匹配了，就输出该字符串
                cout << z << "\n";
                ans++;  //记录匹配名字数
            }
        }
    }
    if(!ans){   //如果没有匹配的有效名字
        cout << "NONE";
    }
    return 0;
}

1.2.3 删除排序数组中的重复项

补一道，发现和洛谷上USACO的题不一样。用数组或者vector都行…反正检测上一个存的是否和本次一样就行，一样就不存了，最后输出下标计数就行。

Code

#include<vector>
#include<iostream>
using namespace std;

int main(){
    vector<int> a;
    int z, i = 1;
    cin >> z;
    a.push_back(z);
    while(cin>>z){
        if(a[i-1]!=z){
            a.push_back(z);
            i++;
        }
    }
    cout << a.size()-1;
}

P1204 [USACO1.2]挤牛奶Milking Cows

这道题我用的差分。可以了解一下。100w的数组是开的下的，所以用一个数组来记录当前时段有多少人在挤奶然后统计下最长无人时间和有人时间就行。注意卡住开始和结束时间，超出该范围的时间不算。

Code

#include<cstdio>
#include<iostream>
using namespace std;

int t[1000010];
int main(){
    int n, ma = 0, ze = 0, on = 0, mi = 1000010; //初始化结束时间，无人时间，有人时间和起始时间。
    cin>>n;
    for(int i=0;i<n;i++){
        int z1,z2;
        cin>>z1>>z2;    //读入时间段
        t[z1]++;        //记录差分
        t[z2]--;
        ma=max(ma,z2);      //更新结束时间
        mi = min(z1, mi);   //更新起始时间
    }
    int ze1=0,on1=0;        //初始化缓存变量
    for(int i=mi;i<=ma;i++){
        t[i]=t[i]+t[i-1];
        if(!t[i]){ze1++;}           //如果当前时间无人，无人时间缓存变量++
        else{ze=max(ze,ze1); ze1=0;} //如果当前时间段有人，则更新最长的无人时间段，并且清零缓存的局部最长无人时间变量。
        if(t[i]){on1++;}    //逻辑同上，改为判断有人时间段即可
        else{on=max(on,on1); on1=0;}
    }
    cout<<on<<" "<<ze;
    return 0;
}

P1205 [USACO1.2]方块转换 Transformations

大大大模拟！ 做得心态有点爆炸，蛮长一模拟。主要解决的问题是旋转90度和翻转的操作，完成了这两个操作其他就没问题了，180和270可以通过多次旋转90度得到。可以直接遍历矩阵完成变换，也可以从矩阵最外层一层一层向里变换。第一种可能会简单些，画出两个矩阵来推关系吧。后面有心情会整理下推导。
以下给出第二种的做法。

Code

#include<cstdio>
#include<iostream>
using namespace std;
char o[10][10], t[10][10], c[10][10];
int n;
void rot90(char b[][10]){                               //旋转90度
    char a[10][10];                                     //缓存数组
    for (int i = 0; i <= n - 2;i++){                    //n-2:层数
        for (int j = i; j < n - i;j++){                 //n-i-1:该层边界，遍历该层一个方向的所有元素
            a[j][n-i-1] = b[i][j];                      //上方换右方        
            a[n - i - 1][n - 1 - j] = b[j][n - i - 1];  //右方换下方
            a[j][i] = b[n - i - 1][j];                  //下方换左方
            a[i][n - 1 - j] = b[j][i];                  //左方换上方
        }
    }
    for (int i = 0; i < n;i++){                         //将缓存覆盖原矩阵
        for (int j = 0; j < n;j++){
            b[i][j] = a[i][j];
        }
    }
}

void reserve(){                                         //翻转操作，题意是关于y轴对称
    for (int i = 0; i < n/2 ;i++){
        for (int j = 0; j < n; j++){
            swap(t[j][i], t[j][n - i - 1]);
        }
    }
}

bool same(char a[][10]){                    //比较矩阵是否和给出的标准矩阵一致
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            if(a[i][j]!=c[i][j]){
                return false;
            }
        }
    }
    return true;
}

int main(){
    int j = 1;
    cin >> n;
    for (int i = 0; i < n;i++){         //读入，并且复制到另一个矩阵，变换时保留原矩阵
        for (int j = 0; j < n;j++){
            cin >> o[i][j];
            t[i][j] = o[i][j];
        }
    }
        for (int i = 0; i < n;i++){     //读入标准矩阵
        for (int j = 0; j < n;j++){
            cin >> c[i][j];
        }
    }
    while (j)               //这个条件不用在意，其实最后还是靠break跳出循环的
    {
        int f = 0;          //标记变量，标记是否该跳出循环
        for (; j < 4;j++){  //旋转90度三次，确认1，2，3的情况
            rot90(t); 
            if(same(t)){    //如果相同，输出是何种情况，并且标记标记变量。
                cout << j;
                f = 1;
                break;
            }
        }
        if(f){break;}       //标记变量为真，跳出
        rot90(t);           //旋转90度，到此旋转360度，又变回原矩阵
        reserve();          //翻转原矩阵
        if(same(t)){        //翻转相同，输出该情况编号，并跳出
            cout << j;
            break;
        }
        for (j = 0; j < 4; j++)//遍历组合可能，逻辑同上
        {
            rot90(t);
            if(same(t)){
                cout << 5;
                f = 1;
                break;
            }
        }
        if(f){break;}
        else if(same(o)){//确认原矩阵相同的情况
            cout << 6;
            break;
        }
        else{           //都不符合，输出7
            cout << 7;
            break;
        }
    }
    return 0;
}

代码还有很多可以优化的地方，比如边旋转边判断，不符合直接跳出，可以节省很多时间。不过这个也能过就是了…

P1206 [USACO1.2]回文平方数 Palindromic Squares

主要搞定俩部分，进制转换和回文判断。
进制转换原理是这样的：以十进制为例，如258。
258%10=8，得到个位数。然后258/10=25，你会发现个位被吞掉了，原来的百位变成了个位。以原数大于0为边界，原数没变成0时反复取模和除法，就能从低位到高位得到这个数每一位的数字。你可以发现，其实除数和模数改变成9时，逐位操作得到的就是9进制下该数字的每一位。所以只要把除数和模数改为基数，就能得到该基数下的数字。不过注意，这样的数字是从低位存到高位的（这边建议字符串储存，方便回文判断），也就是直接输出的数字是反转的。
回文判断就很简单了，从数字左端和右端一起向中间扫描，对比是否一致就行。

Code

#include<cstdio>
#include<iostream>
using namespace std;
char buf[20];
char t[10] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};//建立10以上的数字到字母的映射

int transfer(int n,int b,char buf[]){   //进制转换
    int w = 0, z;                       //w:储存位数
    while (n!=0)
    {   
        z = n % b;
        if(z-9>0){buf[w] = t[z-10];}    //当该位大于10时，映射到字母
        else{buf[w] = z + 48;}
        n /= b;
        w++;
    }
    buf[w] = '\0';
    return w;                           //返回值是位数
}

bool Palindrome(int n){             //判断回文，输入值为位数
    for (int i = 0; i <= n / 2;i++){
        if(buf[i]!=buf[n-i-1]){
            return false;
        }
    }
    return true;
}

int main(){
    char k[20];
    int b;
    cin >> b;
    for (int i = 1; i <= 300;i++){
        if(Palindrome(transfer(i * i, b, buf))){ //所以两个函数可以直接套一起
            int o=transfer(i, b, k);            //转换平方前的数为B进制
            for (int j = o - 1; j >= 0;j--){cout << k[j];}  //倒序输出，因为转换后数字是反转的
                cout << " " << buf << "\n";     //对于是回文的平方数，反转后与原串一致，不用处理
        }
    }
    return 0;
}

P1207 [USACO1.2]双重回文数 Dual Palindromes

上一道题的换皮，没啥好说的了。直接改下上一道题的主程序，函数复制粘贴完事。

Code

#include<cstdio>
#include<iostream>
using namespace std;
char buf[32];

int transfer(int n,int b){
    int w = 0;
    while (n!=0)
    {   
        buf[w] = n % b + 48;
        n /= b;
        w++;
    }
    buf[w] = '\0';
    return w;
}

bool Palindrome(int n){
    for (int i = 0; i <= n / 2;i++){
        if(buf[i]!=buf[n-i-1]){
            return false;
        }
    }
    return true;
}

int main(){
    int n, s, ans = 0;
    cin >> n >> s;
    for (int i = s + 1; ans < n;i++){
        int c = 0;
        for (int j = 2; j <= 10;j++){       //从2到10进制遍历回文可能
            if(Palindrome(transfer(i,j))){
                c++;                        //回文的进制数计数
            }
        }
        if(c>=2){
            cout << i << "\n";              //计数大于2就输出
            ans++;
        }
    }
}

P1208 [USACO1.3]混合牛奶 Mixing Milk

贪心+排序，把所有奶农按价钱从低到高排序，遍历直到满足牛奶需求即可。

Code

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct farmer       //结构体存奶农数据
{
    int price, num;
};

bool cmp(farmer a,farmer b){    //自定义结构体比较函数
    return a.price < b.price;   //小的在前
}
farmer a[5010];

int main(){
    int n, m, ans = 0, milk = 0, c = 0; //ans:花费金额;milk:当前购买的奶量;c:遍历计数器
    cin >> n >> m;
    for (int i = 0; i < m;i++){
        cin >> a[i].price >> a[i].num;
    }
    sort(a, a + m, cmp);
    while (milk<n)      //当购买量小于需求量时继续循环
    {
        ans += a[c].num * a[c].price;   //每个奶农的奶都全买
        milk += a[c].num;
        c++;
    }
    c--;
    if(milk>n){         //处理多出的牛奶，退还金额
        ans -= (milk - n) * a[c].price;
    }
    cout << ans;
}

P1209 [USACO1.3]修理牛棚 Barn Repair

贪心+排序，比上一题要绕个弯。将连在一起的牛棚看作一个整体，显然，这个整体数比间隔数多1。在不考虑木板限制的情况下，毫无疑问，每个整体用一块木板时，长度最短。然后我们发现，每连接一个间隔，需要的木板数就会减少1——所以这道题其实是对间隔贪心排序，优先填补最小的间隔，直到木板数小于等于限制木板数。最后的答案就是填补的间隔总长+有牛的牛棚数量。

Code

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int m, s, c, gap[200], g = 0, ans = 0, cow[201];
    cin >> m >> s >> c;             //其实牛棚总数没用..
    for (int i = 0; i < c;i++){
        cin >> cow[i];
    }
    sort(cow, cow + c);         //有牛牛棚的编号可能不是按顺序输入的，需要排序
    for (int i = 1; i < c;i++){     //计算间隔，存入数组
        if (cow[i] - cow[i-1] > 1)
        {
            gap[g] = cow[i] - cow[i-1] - 1;
            g++;
        }
    }
    sort(gap, gap + g);         //对间隔排序
    int w = g + 1;
    for (int i = 0; w > m;i++){ //对间隔进行贪心选取
        ans += gap[i];
        w--;
    }
    cout << ans + c;            //答案为间隔长+有牛牛棚数
    return 0;
}

P1210 [USACO1.3]最长的回文 Calf Flac

不同于前面两道回文，这道题需要在给定文本中找出回文。最优解法是Manacher算法，O(n)的时间内求解。常规算法就是遍历整个字符串，向每个字符两边扩展回文，需要分奇扩展和偶扩展（奇回文对称中心为回文中心的字符，而偶回文对称中心在中间两个字母之间）。另外这道题的输入也需要用特殊方法处理，详见代码。

Code

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char origin[200010], z[88], tr[200010];
int zpos[2], o[200010], length;

int Palindromej(int c){                     //奇拓展
    int len = 0, i = 1;
    while (c-i>=0 && c+i<length && len<2002) //题目中提到最长回文不超过2000，用暴力枚举交的时候不卡下这个边界可能会超时。反正我交的时候没卡最后个点TLE了Orz。
    {
       if(tr[c-i]==tr[c+i]){len+=2; i++;}
       else{break;}
    }
    i--;
    zpos[0] = o[c - i];     //记录下该回文串在原串中的起始和结束位置
    zpos[1] = o[c + i];
    return len + 1;
}

int Palindromeo(int c){         //偶拓展
    int len = 0, i = 1;
    while (c-i>=0 && c+i-1<length && len<2002)
    {
        if(tr[c-i]==tr[c+i-1]){len+=2; i++;}
        else{break;}
    }
    i--;
    zpos[0] = o[c - i];
    zpos[1] = o[c + i - 1];
    return len;
}

int main(){
    int ma = 0, pos[2], t = 0;
    while (cin.getline(z,88))   //一行一行读入，另这样写程序读到文件结束符EOF会自动结束读入。
    {
        strcat(origin, z);      //将读入的拼接到字符串上去
        strcat(origin, "\n");   //cin不会读入回车，我们手动加上
    }
    for (int i = 0; i < strlen(origin);i++){            //去除非字母字符，顺便统一大小写
        if((origin[i]>='A'&& origin[i]<='Z')||(origin[i]>='a'&& origin[i]<='z')){
            tr[t] = tolower(origin[i]);             //统一大小写
            o[t] = i;                               //记录该字母在原串中的位置
            t++;
        }
    }
    length = strlen(tr);
    for (int i = 1; i < length;i++){        //遍历字符串
        int m = Palindromej(i);
        if(m>ma){                           //回文最长值更新时顺便更新最长字符串起始和终结位置
            ma = m;
            pos[0] = zpos[0];
            pos[1] = zpos[1];
        }
        m = Palindromeo(i);
        if(m>ma){
            ma = m;
            pos[0] = zpos[0];
            pos[1] = zpos[1];
        }
    }
    cout << ma << endl;
    for (int i = pos[0]; i <= pos[1];i++){
        cout << origin[i];
    }
    return 0;
}