Codeforces Round #770 (Div. 2) ABCD题解

思路：
$答案要么1要么2$
$等于1的必要条件是反转之后是它本身$
$反之就是2$
时间复杂度：$On$

#define sf(x) scanf("%d",&x)
#define all(x) (x).begin(),(x).end()
#define cf int _; cin>> _; while(_--)
inline void sf2(int &a , int &b) { sf(a) , sf(b) ;}
signed main()
{cf{int n , m ;sf2(n, m);string s;cin >> s;string ans = s;reverse(all(s));if (s != ans && m)puts("2");elseputs("1");}return 0;
}

思路：
$注意到x和x+3奇偶性不同$

$如果a是奇数，b是偶数$
$假设x是奇数$
$a+=x是偶数$
$b+=x是奇数$
$a\oplus =x是偶数$
$b\oplus =x是奇数$
$x是偶数同理$

$我们发现a和b的奇偶性一直是相对的$
$如果x是偶数ab奇偶性不变$
$如果x是奇数ab奇偶性交换$

$题目最后一句话$
exactly one of your friends could have actually gotten that number.
$说明答案必定存在$
$所以统计奇数个数即可$

$说点题外话，奇偶性这个性质cf经常考，可以多做做类似的题$
时间复杂度：$On$

#define fer(i,a,b) for(int i = a ; i <= b ; ++ i)
#define cf int _; cin>> _; while(_--)
const int N = 1e6 + 10 ;
int n ;
int a[N] , x , y ;signed main()
{cf{cin >> n >> x >> y ;int cnt = 0 ;fer(i,1,n){sf(a[i]) ;if(a[i] & 1) cnt ++ ;}if(x & 1){if(y & 1){if(cnt % 2 == 0) puts("Alice") ;else puts("Bob") ;}else{if(cnt % 2) puts("Alice") ;else puts("Bob") ;}}else {if(y & 1){if(cnt % 2 == 0) puts("Bob") ;else puts("Alice") ;}else{if(cnt % 2) puts("Bob") ;else puts("Alice") ;}}}return 0;
}

思路：
$n是偶数或者k<=1可以，否则都不可以$
时间复杂度：$Onk$

#define fer(i,a,b) for(int i = a ; i <= b ; ++ i)
#define cf int _; cin>> _; while(_--)
signed main()
{cf{int n , k ;cin >> n >> k ;if(n % 2 == 0){puts("YES") ;int cnt = 0 ;for(int i = 1 ; i <= n * k ; i += 2){cnt ++ ;cout << i << " " ;if(cnt == k){cnt = 0 ;puts("") ;}}for(int i = 2 ; i <= n * k ; i += 2){cnt ++ ;cout << i << " " ;if(cnt == k){cnt = 0 ;puts("") ;}}}else if(k <= 1){puts("YES") ;if(k == 1){fer(i,1,n*k){cout << i << "\n" ;}}}else puts("NO") ;}return 0;
}

思路：
$没错,d题想了快2h才做出来$
$有个超级超级重要的性质$
$经过了漫长时间的思考以及草稿纸上的举不出反例才得到的结果$

$第一次假设三个数a[x],a[y],a[z]的下标是1,2,3$

$假设当前差值为last$
$差值就是最大值-最小值,也就是询问x,y,z的结果$

$做2次循环$
$第一次用4到n的每一个数去替换掉第三个数$
$如果当前差值大于等于>=last$
$就替换掉第三个数,同时更新last=当前差值,否则不替换$

$同理，第二次循环替换掉第二个数$
$同时更新last$

$两次循环之后,a[x],a[y],a[z]必定存在0和当前数组中的最大值$
$那怎么找到0和最大值呢$
$有个逻辑是这样的,你找另外一个下标id$

$询问id,y,z的结果$
$如果当前差值=last,说明a[x]一定不是0,那么输出y,z即可$

$同理当前差值!=last,那就用id替换y/z$

$题外话$
$一开始的三个数的下标不一定非得是1,2,3,任意三个不同的下标都可$
$两次循环不一定非得替换第二个数和第三个数，任意2个数皆可$
$这个性质可以在草稿纸上仔细想想推敲推敲$
$个人觉得举不出来反例在算法竞赛当中往往是较为正确的证明$
时间复杂度： O n 2 On^2 On2

#define cf int _; cin>> _; while(_--)
signed main()
{cf{int n ;cin >> n ;int x = 1 , y = 2 , z = 3 ;int last ;cout << "? " << x << " " << y << " " << z << '\n' ;cout.flush() ;cin >> last ;for(int i = 4 ; i <= n ; i ++){cout << "? " << x << " " << y << " " << i << '\n' ;cout.flush() ;int k ;cin >> k ;if(k >= last){last = k ;z = i ;}}for(int i = 1 ; i <= n ; i ++){if(i == x || i == y || i == z) continue ;cout << "? " << x << " " << i << " " << z << '\n' ;cout.flush() ;int k ;cin >> k ;if(k >= last){last = k ;y = i ;}}int id = -1 ;for(int i = 1 ; i <= n ; i ++){if(i == x || i == y || i == z) continue ;id = i ;break ;}int k ;cout << "? " << id << " " << y << " " << z << '\n' ;cout.flush() ;cin >> k ;if(k == last){cout << "! " << y << " " << z << "\n" ;}else {cout << "? " << x << " " << id << " " << z << '\n' ;cout.flush() ;cin >> k ;if(k == last){cout << "! " << x << " " << z << "\n" ;}else{cout << "? " << x << " " << y << " " << id << '\n' ;cout.flush() ;cin >> k ;if(k == last){cout << "! " << x << " " << y << "\n" ;}else cout << "! " << x << " " << y << "\n" ;}}}return 0;
}