A.游戏
（不）排序+乱搞/暴力/二分图/冰茶几（正解） 均可AC
考场上手动模拟了20以内的数据都hack掉了
没想到交上过了
，，，
就挺意外的
B.嘟嘟噜
搞一搞，对于中间不用取模的地方，不再使用加法，而是直接乘过去，调整下标
Code
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
inline void write(register int x){
if(x < 0) x = ~x + 1, putchar('-');
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
signed main(){
freopen("mayuri.in","r",stdin);
freopen("mayuri.out","w",stdout);
register int T = read();
while(T--){
int n = read(), m = read(), x = 0, i = m;
for(register int j = 2; j <= min(n, m); j++)
x=(x+m)%j;
if(n <= m) printf("%d
", x + 1);
else{
x += 1;
while("GARY CSL"){
int nxt = i + (int)ceil(1.0 * (i - x) / (m - 1));
if(nxt > n)break;
x = (x + (nxt - i) * m);
if(x == nxt){
if(++nxt > n) break;
x = (x + m) % nxt;
}else x %= nxt;
i = nxt;
}
x += (n - i) * m;
printf("%d
", x);
}
}
return 0;
}
C.天才绅士少女助手克里斯蒂娜
化简柿子
线段树维护(x^2,y^2,xy)即可
Code
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ls (u << 1)
#define rs (ls | 1)
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
inline void write(register int x){
if(x < 0) x = ~x + 1, putchar('-');
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int ss = 1000010;
const int mod = 20170927;
struct node{
long long xx, yy, xy;
}tr[ss << 2];
struct ANS{
long long a, b, c;
inline void init(){a = 0, b = 0, c = 0;}
inline ANS operator + (const ANS &A) const {
ANS B;
B.a = (long long)(A.a + a) % mod;
B.b = (long long)(A.b + b) % mod;
B.c = (long long)(A.c + c) % mod;
return B;
}
inline void print(){
write((a * b % mod - c * c % mod + mod) % mod);
puts("");
}
};
int a[ss], b[ss];
inline void push_up(register int u){
tr[u].xx = (tr[ls].xx + tr[rs].xx) % mod;
tr[u].yy = (tr[ls].yy + tr[rs].yy) % mod;
tr[u].xy = (tr[ls].xy + tr[rs].xy) % mod;
}
inline void build(register int u, register int l, register int r){
if(l == r){
tr[u].xx = a[l] * a[l];
tr[u].yy = b[l] * b[l];
tr[u].xy = a[l] * b[l];
return;
}
register int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(u);
}
inline void change(register int u, register int l, register int r, register int pos, register int modify_x, register int modify_y){
if(l == r){
tr[u].xx = 1ll * modify_x * modify_x % mod;
tr[u].yy = 1ll * modify_y * modify_y % mod;
tr[u].xy = 1ll * modify_x * modify_y % mod;
return;
}
register int mid = l + r >> 1;
if(pos <= mid) change(ls, l, mid, pos, modify_x, modify_y);
else change(rs, mid + 1, r, pos, modify_x, modify_y);
push_up(u);
}
inline ANS query(register int u, register int l, register int r, register int s, register int t){
if(s <= l && t >= r){
register ANS ans;
ans.a = tr[u].xx;
ans.b = tr[u].yy;
ans.c = tr[u].xy;
return ans;
}
register ANS ans;
ans.init();
register int mid = l + r >> 1;
if(s <= mid) ans = ans + query(ls, l, mid, s, t);
if(t > mid) ans = ans + query(rs, mid + 1, r, s, t);
return ans;
}
signed main(){
freopen("kurisu.in", "r", stdin);
freopen("kurisu.out", "w", stdout);
register int n = read(), m = read();
for(register int i = 1; i <= n; i++) a[i] = read(), b[i] = read();
build(1, 1, n);
while(m--){
register int op = read();
if(op == 1){
register int k = read(), x = read(), y = read();
change(1, 1, n, k, x, y);
}
else{
register int l = read(), r = read();
register ANS ans = query(1, 1, n, l, r);
ans.print();
}
}
return 0;
}
D.凤凰院凶真
维护最长公共上升子序列
学习老姚课件
Code
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ls (u << 1)
#define rs (ls | 1)
using namespace std;
inline int read(){
int x = 0, w = 1;
char ch = getchar();
for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
return x * w;
}
inline void write(register int x){
if(x < 0) x = ~x + 1, putchar('-');
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int ss = 5200;
int n, m, ans, posx, posy;
int a[ss], b[ss];
int f[ss][ss], pre[ss][ss];
inline void Print (register int i, register int j) {
if (i == 0) return;
Print (i - 1, pre[i][j]);
if (f[i][j] != f[i - 1][pre[i][j]]) {
write (b[j]), putchar (' ');
}
}
int main () {
freopen ("phoenix.in", "r", stdin);
freopen ("phoenix.out", "w", stdout);
n = read();
for (register int i = 1; i <= n; i ++) a[i] = read();
m = read();
for (register int i = 1; i <= m; i ++) b[i] = read();
for (register int i = 1; i <= m; i ++) {
if (a[1] == b[i]) f[1][i] = 1;
}
for (register int i = 1; i <= n; i ++) {
if (b[1] == a[i]) f[i][1] = 1;
}
for (register int i = 1; i <= n; i ++) {
register int maxx = 0, k = 0;
for (register int j = 1; j <= m; j ++) {
f[i][j] = f[i - 1][j], pre[i][j] = j;
if (b[j] < a[i] && maxx < f[i - 1][j]) maxx = f[i - 1][j], k = j;
if (a[i] == b[j]) f[i][j] = maxx + 1, pre[i][j] = k;
if (ans < f[i][j]) ans = f[i][j], posx = i, posy = j;
}
}
write (ans), putchar ('
');
Print (posx, posy), putchar ('
');
return 0;
}