Codeforces Round 1069 (Div. 2)

A. Little Fairy’s Painting

ideas:

我感觉题目一点都不好读懂
题目的意思是：要去填充1e181e^{18}1e18个格子，有无限种颜色，给出n个，找规律去填充后面的。
比如案例三：
58 10 15 20 25 5 \\ 8\ 10\ 15\ 20\ 25 \\5810152025
第0个位置的颜色数是8，第一个是10，这样不同的颜色数就是2，每一个数代表不同的颜色，这个案例中就是有5个不同颜色的数。此时第n+1位就填5，此时不同颜色数增加到6（因为5不再原来的数组中）。
后续填充的规则是：不同颜色数作为颜色编号。
那么当，不同颜色数等于前n位颜色编号中的某一位时，不同颜色数就不再增加，答案也就因此固定。

code:

intn;cin>>n;set<int>st;for(inti=0;i<n;i++){cin>>a[i];st.insert(a[i]);}intk=st.size();intans=INT_MAX;for(inti=0;i<n;i++){if(a[i]>=k)ans=min(ans,a[i]);}cout<<ans<<endl;

B. XOR Array

ideas:

题目含义是：
1.在l−rl-rl−r这个区间内的XOR的结果为0；
2.在l−rl-rl−r这个区间外的XOR的结果不为0。
结论：
a[l]⊕a[l+1]⊕...⊕a[r]=pre[r]⊕pre[l−1]a[l] ⊕ a[l+1] ⊕ ... ⊕ a[r] = pre[r] ⊕ pre[l-1]a[l]⊕a[l+1]⊕...⊕a[r]=pre[r]⊕pre[l−1]

推导：
a1⊕a2⊕a3....⊕al....⊕ar=pre[r]a_1\oplus a_2 \oplus a_3.... \oplus a_l.... \oplus a_r = pre[r]a1​⊕a2​⊕a3​....⊕al​....⊕ar​=pre[r]
a1⊕a2⊕a3....⊕al=pre[l]a_1\oplus a_2 \oplus a_3.... \oplus a_l = pre[l]a1​⊕a2​⊕a3​....⊕al​=pre[l]
根据异或的性质：
a⊕a=0a\oplus a = 0a⊕a=0
很轻易得出上面的结论。

要想到答案为0，得出：
pre[r]=pre[l−1]pre[r] = pre[l-1]pre[r]=pre[l−1]

于是我们可以得出构造方法：
1.只需要pre[r]=pre[l−1]pre[r] = pre[l-1]pre[r]=pre[l−1]
2.其他位置的任意，我们选择pre[i]=ipre[i]=ipre[i]=i
3.我们构造的a[i]a[i]a[i]数组是前缀异或值，反解计算出每一位的值。

code:

intn,l,r;cin>>n>>l>>r;vector<int>pre(n+2);for(inti=0;i<n+2;i++)pre[i]=i;pre[l-1]=pre[r];for(inti=0;i<n;i++){cout<<(pre[i]^pre[i+1])<<" ";}cout<<endl;

C. Needle in a Haystack

ideas:

一个模拟题。
思路是：
1.可行性检查：
如果长度一样，一个字符t中没有就输出"Impossible"
如果有一个字符的次数，t中不够，就输出"Impossible"
2.分离字符：
把s中的每一个字符分离出来，剩下的字符串排序
3.合并字符：
对于每一个s中的字符，找到合适的位置放进去就可以
最后把剩余的字符加进去。

code:

string s,t;cin>>s>>t;map<char,int>mpa,mpb;for(autoc:s)mpa[c]++;for(autoc:t)mpb[c]++;//可行性检查for(autoc:s){if(mpb[c]<mpa[c]){cout<<"Impossible"<<endl;return;}}//分离字符string tmp="";for(charc='a';c<='z';c++){intd=mpb[c]-mpa[c];tmp+=string(d,c);}sort(tmp.begin(),tmp.end());//合并字符string ans="";intpos=0;for(autoc:s){while(pos<tmp.size()&&tmp[pos]<c){ans+=tmp[pos];pos++;}ans+=c;}while(pos<tmp.size()){ans+=tmp[pos];pos++;}cout<<ans<<endl;