题解：P11672 [USACO25JAN] Table Recovery S

· · 题解

题解：P11672 [USACO25JAN] Table Recovery S

Preface

这场太我难了。前两题做出来之后本来以为进金稳了，结果剩 45 分钟第三题愣是第一个点都没拿到。痛失 Au。

赛后发现第三题好简单，比前两题既更好想也更好写。

Problem statement

P11672

Solution

这道题突破点就是每个数出现的频率。

只要把初始状态，未被打乱的格子真正画出来我在考场上居然没画就会发现只有两个数只出现一次，也就是 2 和 2n。

这时候还需要发现一个还算挺明显的性质，也就是每行和每列的数在进行完前两种操作后是不会被打乱的，也就是说原来在 2 所在的行里的数在进行完前两种操作后还和 2 在一行。2n 也同理。

最后还需要在观察一下画出来的表格，发现所有和 2 在同一行的数出现次数都不同，所有和 2n 在同一行的数出现次数也各不相同。而且每个数要么在 2 的行里出现过，要么在 2n 的行里出现过。因此我们可以直接通过出现次数确定出每一个数在第三种操作前是什么，也就是确定了答案。

不过还有一点，因为一共有两个数都只出现了一次，我们不知道哪个是 2 哪个是 2n，所以需要把两种可能性的最后结果都算出来，比较字典序，小的那个就是答案。

同时注意这也顺便证明了其实一共只有两种可能的答案。

细节看代码，有大量注释解释。

/*
the forever pain

the key key point to this problem is = 
the frequencies the numbers appear

if you draw the grid out, you'll see that only 2 and 2n appear
exactly once, and another observation that can be made really
easily(as in so easy that I was able to make it incontest) is
that after operations 1 and 2, the elements in a certain row or 
colume won't get mixed up, meaning the numbers that are in the
row 2 was in are still 2, 3, ... n + 1, and same with the colume.

now we've gotta utilize the "frequency" observations again.
this time realizing that each element within the row 2 was
originally in appeared different number of times, for example 3
appear twice, 4, three times, and n + 1 exactly n times.

and we can do the same with elements in the row of 2n(which we can
easily identify because it's one of the only two elements that
appear only once), which include elements n + 1 to 2 * n

and guess what? now we have the whole grid! because now we know
exactly what each elements got switched to what other elements
after operation 3! now there's just one more thing that I haven't
mentioned, it's that we don't know who's 2 and who's 2n, cuz
they both appear once. well we can just construct both
possibilities, and compare the lexicographical order!!!!

一遍过

比t2简单多了, 其实比t1也简单多了 

唉，与 au 失之交臂 
*/
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops")
#define int long long
int n, a[1005][1005], cnt[2005], orig[2005], ans1[1005][1005];
//cnt[i] = how many times i appeared in final table
//orig[i] = what i is originally
int s1, s2;
//only record the row number
signed main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin>>a[i][j];
            cnt[a[i][j]]++;
            //count how many times each element appeared
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(cnt[a[i][j]] == 1){
                if(!s1)s1 = i;
                else s2 = i;
                //find where 2 and 2n are located
            }
        }
    }
    for(int i = 1; i <= n; i++){
        //those are the ones on the same row as 2
        orig[a[s1][i]] = cnt[a[s1][i]] + 1;
        //what it was is just the number of times it appeared + 1       

        //on the same row as 2n
        orig[a[s2][i]] = n * 2 - cnt[a[s2][i]] + 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            ans1[i][j] = orig[a[i][j]];
            //record the answer grid if 2 is s1, so we can
            //compare lexicographical order
        }
    }
    for(int i = 1; i <= n; i++){
        orig[a[s1][i]] = 2 * n - cnt[a[s1][i]] + 1;
        orig[a[s2][i]] = cnt[a[s2][i]] + 1;
        //this time s1 and s2 are reversed
    }
    int opt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(!opt && orig[a[i][j]] != ans1[i][j]){
                if(orig[a[i][j]] < ans1[i][j])opt = 2;
                else opt = 1;
                //find optimal assignment, whether it's the
                //first one(opt = 1) or second one
            }
            if(!opt || opt == 1)cout<<ans1[i][j];
            else cout<<orig[a[i][j]];

            if(j != n)cout<<" ";
            //bruh, usaco!!!
        }
        cout<<endl;
    }
    return 0;
}

After thoughts

Result

其实现在来看这道题其实比这场前两道简单多了，应该只有十二月份 t1 的难度，考场上 45 分钟连想加写完全够了，看来当时应该是被前两题难度给吓到了。