2019.10.03考试解题报告
总结
总体来说能打的暴力都打了
期望(100 + 40 + 30 = 170)
实际(100 + 40 + 40 = 180)
数据良心（其实是数据太水惹）
T1
第一眼觉得就是要找规律，然后直接找找不出来，所以用暴力搜一下
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2011;
int vis[N][N];
struct node {
int x, y, num;
};
const int dx[8] = {-2,-2,-1,1,2,2,1,-1};
const int dy[8] = {-1,1,2,2,1,-1,-2,-2};
queue <node> q;
int sum = 0;
int main() {
for(int T = 0; T <= 100; T++) {
int n = T;
sum = 0;
memset(vis, 0, sizeof(vis));
while(!q.empty()) q.pop();
node st;
st.x = 1000;
st.y = 1000;
vis[st.x][st.y] = 1;
st.num = 0;
q.push(st);
while(!q.empty()) {
node top = q.front();
q.pop();
sum++;
for(int i = 0; i < 8; i++) {
node tmp;
tmp.x = top.x + dx[i];
tmp.y = top.y + dy[i];
tmp.num = top.num + 1;
if(!vis[tmp.x][tmp.y] && tmp.x >= 0 && tmp.y >= 0 && tmp.x <= 2000 && tmp.y <= 2000 &&tmp.num <= n) {
vis[tmp.x][tmp.y] = tmp.num;
q.push(tmp);
}
}
}
cout << sum << '
';
}
}
找不到什么规律，于是求一下差值，还是没什么规律，用差值再求一下差值，发现前五项的差值是特别的，所以直接特别输出，其他的发现差值恒定为(28)，规律就找到啦
(if(n > 5) n -= 4)
(a)数组表示原数列
(a[1] = 325)
(a[2] = 473)
(a[3] = 649)
(a[4] = 853)
(a[5] = 1085)
(b)数组表示差
(b[1] = 148)
(b[2] = 176)
(b[3] = 204)
(b[4] = 232)
(.................)
(b[n] = 120 + n * 28)
显然
(b[2] = b[1] + 28)
(b[3] = b[2] + 28)
(....................................)
(b[n] = b[n - 1] + 28)
有
(a[2] - a[1] = b[1])
(a[3] - a[2] = b[2])
(a[4] - a[3] = b[3])
(a[5] - a[4] = b[4])
(.............................)
(a[n] - a[n - 1] = b[n - 1])
加起来
(a[2] - a[1] + a[3] - a[2] + a[4] - a[3] + .......... a[n] - a[n - 1] = b[1] + b[2] + b[3] + ......... b[n - 1])
去掉多余项，得
(a[n] - a[1] = sum_{i = 1}^{n - 1} b[i])
设(x = sum_{i = 1}^{n - 1} b[i])
所以(a[n] = x + a[1])
x是个等差数列，然后等差数列求和公式为(frac{首项 + 尾项}{2} *数量)
这里就是(frac{b[1] + b[n - 1]}{2} *(n - 1))
所以就是(frac{b[1] + b[n - 1]}{2} *(n - 1) + a[1])
就等于(frac{120 + 28 + 120 + 28 * （n - 1）}{2} *(n - 1) + 325)
然后化简一下，可能爆(long long)，保险起见用(unsigned long long)，然后就做完了
//知识点:宽搜打表找规律
/*
By:Loceaner
找到神奇规律之后发现是等差数列……
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#define ull unsigned long long
using namespace std;
int T;
ull n;
ull a[5] = {1, 9, 41, 109, 205};
int main() {
freopen("horse.in", "r", stdin);
freopen("horse.out", "w", stdout);
scanf("%d", &T);
while(T--) {
cin >> n;
if(n < 5) {
cout << a[n] << "
";
continue;
}
else {
n -= 4;
ull ans = 120 * (n - 1) + 14 * n * (n - 1) + 325;
// ull ans = (240 + 28 * n) / 2 * (n - 1) + 325;
cout << ans << '
';
}
}
return 0;
}
T2
很显然，第一问的答案就是 (2^n)。
第二问的话。。到现在也不会
然后dsr聚聚给我讲了半年，我也不会，上聚聚的代码
#include <bits/stdc++.h>
using namespace std;
const int _=1e5+7;
int n,len,k,vis[_],ans[_];
int main() {
freopen("sensor.in","r",stdin);
freopen("sensor.out","w",stdout);
cin>>k;n=1<<k;
vis[0]=1;
for(int i=n-k+1;i<=n;++i) ans[i]=1;
for(int i=0;i<k;++i) vis[n-(1<<i)]=1;
for(int i=k+1,jt=0;i<=n-k;++i) {
jt=(jt<<1)&(n-1);
if(vis[jt]) ans[i]=1,jt|=1;
vis[jt]=1;
}
printf("%d ",n);
for(int i=1;i<=n;++i) printf("%d",ans[i]);
return 0;
}
T3
第一眼觉得是线段树，因为一列的话挺好操作，可是有十五列，开十五个线段树？？
懵逼了
再加上没有时间写了，于是果断写了暴力，拿了40
下面是40分暴力和修改过的满分代码
//暴力啦啦啦
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
int r, c, q;
char a[50011][20];
char b[50011][20];
int main() {
freopen("holiday.in", "r", stdin);
freopen("holiday.out", "w", stdout);
r = read(), c = read(), q = read();
for(int i = 1; i <= r; i++) {
scanf("%s",a[i]+1);
}
for(int i = 1; i <= r; i++) {
for(int j = 1; j <= c; j++) {
b[i][j] = '0';
}
}
while(q--) {
int cnt = 0;
int u1 = read(), v1 = read(), u2 = read(), v2 = read();
char col;
cin >> col;
for(int i = u1; i <= v1; i++) {
for(int j = u2; j <= v2; j++) {
b[i][j] = col;
}
}
for(int i = 1; i <= r; i++) {
for(int j = 1; j <= c; j++) {
if(a[i][j] == b[i][j]) cnt++;
}
}
cout << cnt << '
';
}
return 0;
}
修改后
//知识点:多个线段树
/*
By:Loceaner
第一眼线段树，第二眼不会打
第三眼打暴力，最后多了10分
数据良心
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e4 + 11;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
char a[N][20];
int r, c, q;
#define lson rt << 1
#define rson rt << 1 | 1
struct seg_tree{
struct node {
int siz, tot, ans, tag;
} t[N << 2];
void build(int l, int r, int rt, int k) {
t[rt].tag = -1;
t[rt].siz = r - l + 1;
if(l == r) {
t[rt].tot = (a[l][k] == '1');
t[rt].ans = (a[l][k] == '0');
return;
}
int mid = (l + r) >> 1;
build(l, mid, lson, k);
build(mid + 1, r, rson, k);
t[rt].tot = t[lson].tot + t[rson].tot;
t[rt].ans = t[lson].ans + t[rson].ans;
}
void tag(int rt, int ad) {
if(ad == 1) t[rt].ans = t[rt].tot;
else t[rt].ans = t[rt].siz - t[rt].tot;
t[rt].tag = ad;
}
void pushdown(int rt) {
if(t[rt].tag != -1) {
tag(lson, t[rt].tag);
tag(rson, t[rt].tag);
t[rt].tag = -1;
}
}
void update(int L, int R, int k, int l, int r, int rt) {
if(L <= l && r <= R) {
tag(rt, k);
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if(L <= mid) update(L, R, k, l, mid, lson);
if(R > mid) update(L, R, k, mid + 1, r, rson);
t[rt].ans = t[lson].ans + t[rson].ans;
}
} T[16];
int main() {
freopen("holiday.in", "r", stdin);
freopen("holiday.out", "w", stdout);
r = read(), c = read(), q = read();
for(int i = 1; i <= r; i++) scanf("%s", a[i] + 1);
for(int i = 1; i <= c; i++) T[i].build(1, r, 1, i);
while(q--) {
int L = read(), R = read(), u2 = read(), v2 = read(), col = read();
for(int i = u2; i <= v2; i++) T[i].update(L, R, col, 1, r, 1);
int ans = 0;
for(int i = 1; i <= c; i++) ans += T[i].t[1].ans;
cout << ans << '
';
}
return 0;}