| Educational Codeforces Round 48 (Rated for Div. 2) |
|---|
C. Vasya And The Mushrooms
题目链接：https://codeforces.com/contest/1016/problem/C
题意：
emmm，说不清楚，还是直接看题目吧。
题解：
这个题人行走的方式是有一定的规律的，最后都是直接走到底，然后从另外一行走回来。并且通过画图观察，会发现他走到格子的时间会有一定的规律。
所以就维护几个前缀和就行了，从1到n枚举一下，还要维护一下目前走过的格子对答案的贡献，如果是奇数那么当前就是从上面出发，如果是偶数就是从下面出发，计算答案的时候根据规律来就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + ;
int n;
ll a[][N], sum123[][N], sum321[][N], sum[][N];
int main() {
ios::sync_with_stdio(false);
cin.tie();
cin >> n;
for(int i = ; i < ; i++) {
for(int j = ; j <= n; j++) {
cin >> a[i][j];
}
}
for(int i = ; i < ; i++) {
for(int j = n; j >= ; j--) {
sum[i][j] = sum[i][j + ] + a[i][j];
sum123[i][j] = sum123[i][j + ] + (ll)(j - ) * a[i][j];
sum321[i][j] = sum321[i][j + ] + (ll)(n + n - j) * a[i][j];
}
}
ll S = , ans = , Sum = , now = ;
ll cnt = , cur = ;
for(ll j = ; j <= n; j++) {
Sum += sum123[cur][j + ] + (j - ) * sum[cur][j + ];
Sum += sum321[cur ^ ][j] + (j - ) * sum[cur ^ ][j];
ans = max(ans, Sum);
now += a[cur ^ ][j] * cnt; cnt++;
now += a[cur ^ ][j + ] * cnt; cnt++;
Sum = now;
cur ^= ;
}
cout << ans;
return ;
}
D. Vasya And The Matrix
题目链接：https://codeforces.com/contest/1016/problem/D
题意：
给出每一行和每一列的异或值，要求你构造一个矩阵满足这个异或值。
题解：
这个构造还是挺巧妙的，首先先把a2...an和b2,b3...bm安排好，然后对于(1,1)这个位置，构造a1^b2^b3...^bm，其余全是0就行了，这个还是比较容易证明的。
反正就是很巧妙。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
ll a[N], b[N];
int n, m;
int main() {
ios::sync_with_stdio(false);
cin.tie();
cin >> n >> m;
ll cur = ;
for(int i = ; i <= n; i++)
cin >> a[i], cur ^= a[i];
for(int i = ; i <= m; i++)
cin >> b[i], cur ^= b[i];
if(cur != ) {
cout << "NO";
return ;
}
cout << "YES" << '\n';
cur = a[];
for(int i = ; i <= m; i++)
cur ^= b[i];
cout << cur;
for(int i = ; i <= m; i++)
cout << ' ' << b[i];
cout << '\n';
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(j == )
cout << a[i];
else
cout << ' ' << ;
}
cout << '\n';
}
return ;
}