Codeforces Round #770 (Div. 2)思路分享

Codeforces Round #770 (Div. 2)

这次的cf让我知道了手玩样例的重要性，多举点例子，说不定就能找到规律呢。

A. Reverse and Concatenate

给定字符串s，进行若干次操作，令t=s的反过来。每次操作令s=s+t或s=t+s。问k次操作后，能得到多少个不同的字符串。可以发现无论是s=s+t还是s=t+s.得到的字符串s一定是回文的。那么回文串的t就和s相等，那么两种方式本质上就没什么区别了，无论进行多少次，最多得到2种字符串。注意特判下刚开始的字符串是否为回文的即可。

B. Fortune Telling

这个题真的卡了我许久...觉得题目将3换成1，感觉提示就更明显了。一直在纠结+和^的性质....
我们可以发现3的二进制为11，那么x和x+3的二进制的末位上的数字一定不同。然后可以发现，+和^{都是加法(}是不进位加法)，所以同样一个数,我们无论用哪种操作，末位上的数字总是相同的。这样的话，我们直接从x开始，一直异或\(a_i\)，看末位上的数字是否和y相同即可。

C. OKEA

感觉这个题没上个题难想，其实这个题看上去很难。但通过手玩几个样例可以发现，同一行上面的数字，只能是依次加2，即1,3,5,7，..，或者2,4,6,8,10...，只有这样，任何一个区间的平均数才都是整数。这样的话，我们直接统计下奇数偶数的数量，看能不能恰好填充即可。

D. Finding Zero

不说了，先看图：

由于思路不是很清晰以及对交互题的不熟悉，这个题真的是莽出来的....
由于这个原因，才会出现
我四道题没有一个三道题的排名高,呜呜呜....
我们看题面，就知道这种构造题，最后的方法一定是用到2n-2次才能搞出来答案。
首先看到\(max(a_i,a_j,a_k)-min(a_i,a_j,a_k)\)我们知道整个序列有两个值最重要，最大值和最小值。最小值毋庸置疑，题目明确说了只有一个0，最大值我们是未知的。完全不知道什么性质的情况下，我们可以举例子，发现下有什么性质。我们可以先固定\(a_1,a_2\)，我们假设，\(a_1然后一直询问\(a_3-a_n\),发他们的值是否有什么规律，或者对我们有什么用。我们可以发现，如果\(a_i\)的值在\(a_1,a_2\)之间的话，那么返回的值就是\(a_2-a_1\)。否则，如果值在两侧的话，分别就是\(a_i-a_1\)或\(a_2-a_i\)。通过这样的话，我们会发现，最大的值所对应的\(a_i\)。一定是最大值或0。同时还有一种特殊情况，就是1,2分别是最小值和最大值，那样的话，其他所有值询问的结果都一样。既然这样，我们找到的第i个数，可能是最大值或0，也有可能啥也不是，那我们保留1和i，这样的话，我们可以确定的是，这两个数中至少有一个是最大值和最小值，但我们不知道是哪一个。保留这两个，我们再一直询问，其他所有的数，这样的话，我们一定能将另一个最大值或最小值找出来。这里的特殊情况是，若1和i恰好为0和最大值的话，我们找到的id，就啥也不是了。但我们可以肯定是1，i和id。这三个数一定有两个是最大值和0.发现我们已经用了2n-4次操作，接下来我们随便找个j，询问1，i，j
和1,j,id.用这个值，和刚才我们找id时保留的最大值比较。那个是，就说明哪两个是最大值和最小值。都不是就说明id和idd是。

#include
using namespace std;
int n,T;
int main()
{
//    freopen("1.in","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int id=3,ans=0;
        for(int i=3;i<=n;++i)
        {
            printf("? %d %d %d\n",1,2,i); 
            fflush(stdout);
            int x;scanf("%d",&x);
            if(x>ans) ans=x,id=i;
        }
        int idd=2;ans=0;
        for(int i=2;i<=n;++i)
        {
            if(i==id) continue;
            printf("? %d %d %d\n",1,id,i); 
            fflush(stdout);
            int x;scanf("%d",&x);
            if(x>ans) ans=x,idd=i;
        }
        for(int i=2;i<=n;++i)
        {
            if(i!=idd&&i!=id) 
            {
                printf("? %d %d %d\n",i,1,idd); 
                fflush(stdout);  
                int ps;scanf("%d",&ps);
                printf("? %d %d %d\n",i,1,id); 
                fflush(stdout);
                int rs;scanf("%d",&rs);
                if(ps==ans)
                {
                    printf("! %d %d\n",1,idd);
                    fflush(stdout);
                }
                else if(rs==ans) 
                {
                    printf("! %d %d\n",1,id);
                    fflush(stdout);
                }
                else
                {
                    printf("! %d %d\n",id,idd);
                    fflush(stdout);
                } 
                break;     
            } 
        }   
    }
    return 0;
} 

E. Fair Share

这个题看起来也很好玩。..考虑什么情况下会不合法，题目要求最终构成两个相同的集合。所以若有某个数字只出现了奇数次，则一定不合法。接下来考虑每个数字出现了偶数次的情况。由于每个序列都有偶数个数，且这些数一半是L一半是R，倘若我们将每个序列看做一个点，每个数看作一条边，L和R代表出度与入度，则代表一半入读一半出度。再考虑每个点都有偶数个边。那么最终形成的就是欧拉回路的问题...我也是第一次遇见这样的问题....

#include
using namespace std;
const int N=2e5+10;
int m,cnt[N],b[N],num;
vectorv[N],ans[N];
map,bool>mp[N<<1];
inline int find(int x){return lower_bound(b+1,b+num+1,x)-b;}
inline bool check()
{
    for(int i=1;i<=num;++i) if(cnt[i]%2==1) return true;
    return false; 
}
inline void dfs(int x)
{
    int ts=0;
    for(auto s:mp[x])
    {
        int y=s.first.first,id=s.first.second;
        if(y>m) ans[x][id]=1;
        mp[x].erase({y,id});
        mp[y].erase({x,id});
        ts=y;break;
    } 
    if(ts) dfs(ts);
}
int main()
{
//    freopen("1.in","r",stdin);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        int x;scanf("%d",&x);
        for(int j=1;j<=x;++j)
        {
            int y;scanf("%d",&y);
            v[i].push_back(y);
            ans[i].push_back(0);
            b[++num]=y;
        }
        ans[i].push_back(0);
    }
    sort(b+1,b+num+1);
    num=unique(b+1,b+num+1)-b-1;
    for(int i=1;i<=m;++i)
    {
        for(int j=0;j