比赛网站:https://codeforc.es/contest/1699
这次比赛一道题都没有做出来,A题很像acm省赛第一题那种规律题,B题很像第一次参加泉城赛的矩阵题(都是推导公式)。C题是个区间问题,感觉也不好做。这里只看前三题。
A题:大意就是输入一个数n,然后找到三个数,让它们两两异或相加等于n
这个题当时我看出来了如果是奇数,那么就没有解输出-1。同时我也考虑到了可以找两个相等的数制作0,然后让这个数和第三个数异或出n/2,但是我始终没有把这两个相同的数用0来做实验。昨天的时候一直自认为数据范围是大于1的,读题没有读好,考虑的也不够周到。导致这次周赛卡题了
solution:为偶数则 输出两个0和一个n/2,因为0异或任何数都是原来的数。奇数直接输出-1。
code:
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; if(n%2) { cout<<-1<<endl; }else { cout<<0<<' '<<0<<' '<<n/2<<endl; } } }B题:大意就是给出一个棋盘,里面有黑子和白字,你需要填充它,然后保证白子的上下左右有两个是白子,黑子的上下左右有两个是黑子。
一个思维的推导题,很难思考出来。
solution:可以以这么一个基本图形作为基础进行扩展,然后我们去推断这个基本图形黑白子所对应的 公式
我们可以直接列举一下其中一个颜色的 i=1,j=1 ;i=1,j=4; i=4,j=1; i=4,j=4; 这四种情况,i%4=1和=0时 同时满足 j%4=1和j%4=0时 ,这个情况是黑子。 i=2,j=2;i=2,j=3; i=3,j=2; i=3;j=3 ; 这里的情况是什么?i%4=2和=3 同时满足 j%4=2和=3 也就是说
if(i%4<2&&j%4<2 || i%4>=2&&j%4>=2) 这个情况下可以是黑子,那么else就是白子了,因为||前面是两种情况,后面是两种情况(这个公式自己推出来了,不过说实话,cf的大佬压行的代码看着是真难受)
不过最难的一点就是,这个基本图形需要自己有思路去构造出来。这里感觉可以用第一个测试例子,然后来翻转找一个思路。如果明白了基本图思想,能够想到四四结合能构造上下左右有两个同色的,应该就可以构造出基本图形来。
code:
#include<bits/stdc++.h> using namespace std; int main() { int n,m,t,i,j; cin>>t; while(t--) { cin>>n>>m; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(i%4<2&&j%4<2 || i%4>=2&&j%4>=2) cout<<1<<' '; else cout<<0<<' '; } cout<<endl; } } }
C题:一个区间的构造问题。大意是给出一个数组a 里面元素是0-n-1的乱序,我们约定mex(l,r) 的值是没有出现在l到r元素的最小非负整数。然后要求我们构造出个数组b,对于数组b的任意区间l和r ,都有mexa(l,r) = mexb(l,r)。要求我们求出数组b的个数。结果mod一个数
这个题很容易让人看着没有头绪,不知道从哪里开始入手。尤其是这种结果要mod一个数的题,处理不好很容易TLE。凡要mod,必有巧。
solution:先考虑0的位置,因为如果范围内只有0,那么mex =1,所以如果0的位置不一样一定pass。确定好0的位置后,我们在利用0的位置来确定1,因为0周围的区间如果不包含1,那么一定会是1。省下的晚点更,希望早点弄的明白些
———————————— 半小时后~ ——————————————————————————————————————————————
今天必须弄明白!!!
这个题是这样的,前面说了我们很容易得出01必须和数组a保持一直。那么我们一个个来考虑,考虑到2数字,2如果在01区间内,那么2的位置可以放到几个位置,答案是 r-i+1区间数 减去确定的 两个数,这个数正好和i相等。那么可以是r-i+1-i 。这里根据排列组合我们不难想出是需要进行乘法运算。那么如果是区间外呢,那么我们必须保证和原来的数组a位置一直,因为01区间加上周围的数组成的区间,它的mex我们必须要让他和原来数组a保持一致,如果2的位置发生了变化,那么就无法维护原来区间的mex值。3之后的数同理。
这里我们直接看大佬的代码:https://www.cnblogs.com/gosick-ll/p/16445509.html
code:
#include <bits/stdc++.h> using namespace std; #define endl "\n" typedef long long ll; const ll N = 1e5, mod = 1e9 + 7; void solve() { int n; cin >> n; int sf[n]; vector<int> s(n); for (int i = 0; i < n; i++) { cin >> sf[i]; s[sf[i]] = i; } int l = s[0], r = s[0]; ll ans = 1; for (int i = 1; i < n; i++) { if (s[i] > r) r = s[i]; else if (s[i] < l) l = s[i]; else ans = ans * (r - l + 1 - i) % mod; } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t; cin >> t; while (t--) solve(); return 0; }
重点在于这个if else 。如果在已知区间范围内,我们套用之前的那个公式累乘法,否则,我们尝试更新区间,因为不在区间内的方法只有一种。无需更新。
重写了一遍code:
#include<bits/stdc++.h> using namespace std; const int maxt = 1e5; const int mod = 1e9+7; int main() { int t; vector<int>pos(maxt); cin>>t; while(t--) { pos.clear(); int n,x; long long ans=1; cin>>n; for(int i=0;i<n;i++) { cin>>x; pos[x] = i; } int l=pos[0],r=pos[0]; for(int i=1;i<n;i++) { if(pos[i]<l) l = pos[i]; else if(pos[i]>r) r = pos[i]; else ans = ans%mod*(r-l+1-i)%mod; } cout<<ans<<endl; } }