Codeforces AIM TECH Round 4 (Div 2) 题解 (ABCD)

写在前面

我的第六篇博客，记录我在cf第七场比赛。
一共AC了两题：B和C。
被hack了两次，而A是在锁了之后被hack成功的。
排名1351，分数 1530->1505，很难受。

844A. Diversity （模拟）

给定字符串s ( |s|<=1000 ) 和k(1<=k<=26),输出最少将s中的字符更改几个可以使s中有k个以上的不同字符,不可能则输出impossible.

若|s|<k,显然不可能.
统计s中不同的字符个数t,输出min(k-t,0)即可.
写程序时,统计s中重复的字符个数z比较简便,输出min(k-(s-z),0)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[200];
char s[1010];
int main(void)
{
    int k,z=0;
    scanf("%s",s);
    scanf("%d",&k);
    if(strlen(s)<k)
        printf("impossible\n");
    else
    {
        for(int i=0;i<strlen(s);i++)
        {
            if(a[s[i]]==0)
                a[s[i]]++;
            else
                z++;
        }
        printf("%d\n",max(0,k-(int)(strlen(s)-z)) );
    }
    return 0;
}

代码用时 6分钟.
比赛时,没有考虑到结果可能为负,被hack.

844B. Rectangles (模拟)

给定n,m(50),和一个n*m的01矩阵,输出矩阵中有多少个集合.
集合的定义是:数字相同且所有数字在同一行或同一列.

依次组合发现,结果为每行每列2^(1的个数)-1+2^(0的个数)-1,最后减去n*m(单元素集合计算了两次),上限为100*2^50,在int以上ll以下.

#include <cstdio>
#include <iostream>
using namespace std;
int a[51],b[51];
int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        int tmp;
        scanf("%d",&tmp);
        if(tmp)
        {
            a[i]++;
            b[j]++;
        }
    }
    long long ans=0,ll1=1;
    for(int i=0;i<n;i++)
    {
        ans+=(ll1<<a[i])+(ll1<<(m-a[i]))-2;
    }
    for(int i=0;i<m;i++)
    {
        ans+=(ll1<<b[i])+(ll1<<(n-b[i]))-2;
    }
    ans-=m*n;
    cout << ans <<endl;
    return 0;
}

代码用时:6分钟.
坑点:int常数左移若干位的结果会赋在int中,可能会超界.比赛时因为这个被hack了一次.

844C. Sorting by Subsequences (离散化,序列环)

给定n(1e5)和n个互不相同的整数(±1e9),将他们按数量最多的子序列排序.输出子序列个数和每个子序列的长度及具体内容.
按子序列排序的意思是将原序列离散化后分成若干个子序列,每个数仅能出现在一个中,将子序列排序,最后按分开时的顺序合并即得到排序后的原序列.

离散化后,遍历整个序列,找到各个环即可.
可以说是一道离散化和找环的模板题.

#include <bits/stdc++.h>
using namespace std;
const int M=100010;
int a[M],b[M];

//离散化,传入原数组,存放数组,长度.
template <class Typename> void discre(Typename *src, Typename *des, int n)
{
    map<int, int> mp_discre;
    memcpy(des, src, n * sizeof(stc[0]));
    sort(des, des + n);
    for(int i = 0; i < n; i++)
        mp_discre[des[i]] = i + 1;
    for(int i = 0; i < n; i++)
        des[i] = mp_discre[src[i]];
}

//需要按照原顺序,可以改用vector
set <int> saveloop[M];

//传入需要找环的数组和长度,会被改变.结果储存在saveloop里,返回环数
template <class Typename> int findloop(Typename *a,int n)
{
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int p=i;
        while(a[p])
        {
            //do something
            saveloop[ans].insert(a[p]);
            int last = p;
            p=a[p]-1;
            a[last] = 0;
        }
        if(!saveloop[ans].empty())
            ans++;
    }
    return ans;
}

//传入环数,自动从saveloop调用
void printloop(int ans)
{
    printf("%d\n",ans );
    for(int i=0;i<ans;i++)
    {
        int len=saveloop[i].size();
        printf("%d",len );
        for(auto j:saveloop[i])
            cout <<' ' << j;
        printf("\n");
    }
}
int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    discre(a,b,n);
    int ans=findloop(b,n);
    printloop(ans);
    return 0;
}

代码用时:5分钟(调用新写的模板).
比赛AC时间:50分钟.

844D. Interactive LowerBound (交互题,随机)

给定一个长为n(50000)的单链表,以及他的开头的位置start,需要查找的数x,通过最多2000次交互求x的lower_bound.
单链表:若干个存放两个数的位置:值vi,下个数的位置nexi,保证v(nexi)>vi,(1<=n<=n).
交互两种操作:
输出 ? i 会给出vi和 nexi,当vi是最大时nex=-1.(最多1999次)
输出 ! ans ,表示给出结果.
每次输出后需要调用fflush(stdout).

首先明确要求,lower_bound需要找到大于等于x的第一个值,即如果vi<x且v(nexi)>=x,答案就是v(nexi).
进行一次(? start),特判一次.然后随机999个i输出(? i),选择返回的结果里最大的小于等于x的值.从该值开始求最多999个nex,找到lower_bound(x)或者-1停止.
概率分析:随机时只要随机到[x的排序-999,x的排序]之内的任意一个数即可,一共有n个数,找不到的概率为(1-999/n)^999,代入n=50000计算,约为1e-9(0.00000000175)

#include <bits/stdc++.h>
using namespace std;
int sec(int a, int b, int x)
{
    if(a > b && a <= x)
        return 1;
    return 0;
}
pair<int, int> get(int index)
{
    printf("? %d\n", index );
    fflush(stdout);
    int tv, tn;
    scanf("%d %d", &tv, &tn);
    if(tv == -1 && tn == -1)
        exit(0);
    return {tv, tn};
}
int main(void)
{
    srand(time(0));
    int n, start, x, time = 999;
    scanf("%d%d%d", &n, &start, &x);
    pair<int, int> now = get(start), tmp;
    if(now.first >= x)
    {
        printf("! %d\n", now.first );
        return 0;
    }
    for(int i = 1; i < 1000; i++)
    {
        tmp = get((rand() + rand()) % n + 1);
        if(sec(tmp.first, now.first, x))
            now = tmp;
    }
    tmp = now;
    while(time--)
    {
        if(tmp.first <= x && now.first >= x)
        {
            printf("! %d\n", now.first);
            return 0;
        }
        if(now.second == -1)
            break;
        tmp = now;
        now = get(tmp.second);
    }
    printf("! -1\n");
    return 0;
}

下午写的代码,但是陷入了一个比较难察觉的逻辑bug中,晚上才找到.
写题之前还通过群里讨论避免了一个bug:cf的rand()似乎只能到32767.
考虑一下以后把逻辑图先画好?
代码用时(如果没有逻辑bug):40分钟
debug时间:2小时.

总结

常数移位也会溢出,程序的需求与逻辑结构一定要理清楚.
关于cf:锁题也在一定程度上意味着失去了被hack帮忙找bug的机会.
rand()最大值32767.,可以通过乘或加来实现大数的随机.