orz 首先说一下这个只是民间题解，可能会有很多错误
程序还没有评测，所以可能存在问题
C题比赛的时候没想到。。后来发现是个模板题，所以没有代码
希望这份题解能对读者有所启发吧。。。
A题
直接倒序枚举即可
因为一个数n最短减sqrt(n)次就可以变成回文数
所以复杂度是sqrt(n)的
（也可以利用字符串做法，会更快）
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline bool ok(int x){
int a[10], n = 0;
while(x != 0){
a[n++] = x%10;
x/=10;
}
for(int i = 0; i < n; i++){
if(a[i] != a[n-i-1]) return false;
}
return true;
}
int huiwen(int x){
for(int i = x; i >= 0; i--){
if(ok(i)) return i;
}
return 0;
}
int x;
int main(){
cin>>x;
if(x == 0) { cout<<x<<endl; return 0; }
while(x != 0){
int y = huiwen(x);
if(y == 0) break;
cout<<y<<endl;
x -= y;
}
}
B题
动态规划，不妨设当前已经规划完了前面i个点的分配方案
即dp[i][m]表示从第i点以后要用m条边来匹配，所能获得的最大权值
那么如果一个方案合法就必须满足，之前的分配数x和y之间有
x - (i-1)*(i-2) <= y 也就是之前区间相互连接，这样会使与后方连的边尽量少
那么如果x - (i-1)*(i-2) > y ，意思就是之前区间不管如何连接，后方不可能与前方匹配
比如4 4 4 2 2这种情况， 后面的2个2是无法与前面的3个4匹配，即不合法
还有就是后面每个都至少分配一条边
所以每次dp都需要判断一下这两个条件
然后我们还可以发现，我们只需要给出一个2*m的合法拆分方案，就是一个合法的解，跟给出顺序是无关的
所以不妨设第一个点分配最多的边，剩下的大小也是按照次序的
这样会给dp带来很大方便
然后利用记忆化搜索来dp就很好写了
（代码中注释掉的那一部分可以给出一个方案）
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
LL dp[501][2002], a[501], G[501][2002], H[501][2002];
int n, m, M;
const LL inf = 1e8;
LL dfs(int x, int m, int Max){
if(n-x+1 > m) return -inf;
if(M - m - (x-1)*(x-2) > m) return -inf;
if(x == n)
if(m <= n-1 && m <= Max) return a[m];
else return -inf;
if(H[x][m] > 0) return dp[x][m];
H[x][m] = 1;
for(int i = min(n-1, min(Max, m)); i >= 1; i--){
int k = dfs(x+1, m-i, i) + a[i];
if(k > 0){
if(k > dp[x][m]){
dp[x][m] = k;
G[x][m] = m-i;
}
}
}
return dp[x][m];
}
int main(){
cin>>n>>m; M = 2*m;
for(int i = 1; i < n; i++) cin>>a[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= 2*m; j++)
dp[i][j] = -inf;
cout<<dfs(1, 2*m, m)<<endl;
/*int x = M;
for(int i = 1; i <= n; i++){
cout<<G[i][x]<<" ";
x = G[i][x];
}*/
}
C题
费用流，最长K可重区间集问题
模板题
见http://hzwer.com/5842.html
D题
计算几何
不妨先把凸多边形的每条边，往它的单位向量的法向量方向平移r的长度
这样构成了一个新的凸多边形，
在这个新的凸多边形求最远的那两个点就是答案
构成新的凸多边形的过程需要用到半平面交算法（模板）
求最远的两个点需要用到旋转卡壳算法（模板）
所以就是模板题
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 200500;
const double eps = 1e-7;
struct Vector{
double x, y;
Vector(double _x=0, double _y=0):x(_x), y(_y) {}
double len() { return sqrt(x*x + y*y); }
Vector operator /(double v){ return Vector(x/v, y/v); }
Vector operator *(double v){ return Vector(x*v, y*v); }
void print(){
cout<<x<<" "<<y<<endl;
}
}points[maxn], pp[maxn], px, py;
typedef Vector Point;
Vector operator - (Vector A, Vector B)
{ return Vector(A.x - B.x, A.y - B.y); }
Vector operator + (Vector A, Vector B)
{ return Vector(A.x + B.x, A.y + B.y); }
Vector operator < (const Point &A, const Point &B)
{ return (A.x == B.x) ? A.y < B.y : A.x < B.x; }
double Distance(Point A, Point B)
{ return sqrt(pow(A.x - B.x, 2) + pow(A.y - B.y, 2)); }
struct Line{
Point p;
Vector v;
double ang;
Line() {}
Line(Point A, Point B){
p = A;
v = (A-B)/Distance(A, B);
ang = atan2(v.y, v.x);
}
bool operator <(const Line &L) const { return ang < L.ang; }
}lines[maxn];
double Cross(Vector A, Vector B)
{ return A.x*B.y - A.y*B.x; }
bool OnLeft(Line L, Point p){
return Cross(L.v, p - L.p) > 0;
}
Point GetIntersection(Line a, Line b){
Vector u = a.p - b.p;
double t = Cross(b.v, u)/Cross(a.v, b.v);
return a.p+a.v*t;
}
int HalfplaneIntersection(Line *L, int n, Point *poly){
sort(L, L+n);
int first, last;
Point *p = new Point[n];
Line *q = new Line[n];
q[first = last = 0] = L[0];
for(int i = 1; i < n; i++){
while(first < last && !OnLeft(L[i], p[last-1])) last--;
while(first < last && !OnLeft(L[i], p[first])) first++;
q[++last] = L[i];
if(fabs(Cross(q[last].v, q[last-1].v)) < eps){
last--;
if(OnLeft(q[last], L[i].p)) q[last] = L[i];
}
if(first < last) p[last-1] = GetIntersection(q[last-1], q[last]);
}
while(first < last && !OnLeft(q[first], p[last-1])) last--;
if(last - first <= 1) return 0;
p[last] = GetIntersection(q[last], q[first]);
int m = 0;
for(int i = first; i <= last; i++) poly[m++] = p[i];
return m;
}
int n, r;
int main(){
cin>>n>>r;
cin>>points[0].x>>points[0].y;
for(int i = 1; i < n; i++){
cin>>points[i].x>>points[i].y;
lines[i-1] = Line(points[i-1], points[i]);
}
lines[n-1] = Line(points[n-1], points[0]);
for(int i = 0; i < n; i++){
Vector v = lines[i].v;
v = Vector(-v.y, v.x);
v = v/v.len();
lines[i].p = lines[i].p + v*r;
//lines[i].p.print();
}
int N = HalfplaneIntersection(lines, n, pp);
pp[N] = pp[0];
int now = 1;
double ans = 0;
//cout<<N<<endl;
for(int i = 0; i < N; i++){
while(Cross(pp[i+1]-pp[i], pp[now]-pp[i]) < Cross(pp[i+1]-pp[i], pp[now+1]-pp[i])){
now++;
if(now == N) now = 0;
}
if(Distance(pp[now], pp[i]) > ans){
ans = Distance(pp[now], pp[i]);
px = pp[now]; py = pp[i];
}
}
cout<<px.x<<" "<<px.y<<" ";
cout<<py.x<<" "<<py.y<<endl;
}
E题
bfs问题
利用宽度优先搜索和哈希判重，可以很快做出来
因为状态数 9!只有10^5的数量级
这样可以得到很多分数，但是询问过多，也会超时
所以直接以最后的结果为根，然后建立一个搜索树
这样每次查询都是询问父亲到根的一条链
因为深度不超过32
所以每次查询的复杂度也就只有O(32)
就可以通过了
（如果发现结点不在树上，就是无解）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
typedef pair<int, int> PII;
const int MOD = 123456;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const char ch[4] = {'u', 'l', 'd', 'r'};
vector<char> V;
vector<PLI> G[MOD+1];
vector<PII> pa;
LL Pow[20];
LL get(int r, int c){
return Pow[(2-r)*3 + (2-c)];
}
void Hinsert(LL x, int v){
G[x%MOD].push_back(mp(x, v));
}
int Hfind(LL x){
for(int i = 0; i < G[x%MOD].size(); i++){
PII u = G[x%MOD][i];
if(u.fi == x) return u.se;
}
return -1;
}
void Herase(){
for(int i = 0; i < MOD; i++) G[i].clear();
}
int n, tot, x;
LL nowS;
queue<PLI> Q;
queue<PII> Qxy;
int main(){
freopen("我钦定wps第一", "r", stdin);
Pow[0] = 1;
for(int i = 1; i < 12; i++) Pow[i] = Pow[i-1]*10;
Q.push(mp(123456780, 0));
Qxy.push(mp(2, 2));
Hinsert(123456780, 0);
pa.push_back(mp(0, 0));
while(!Q.empty()){
PLI x = Q.front(); Q.pop();
PII loc = Qxy.front(); Qxy.pop();
if(x.se >= 1000) break;
//cout<<x.fi<<endl;
for(int i = 0; i < 4; i++){
int newx = loc.fi + dx[i];
int newy = loc.se + dy[i];
if(newx < 0 || newx > 2) continue;
if(newy < 0 || newy > 2) continue;
int t = x.fi/get(newy, newx)%10;
LL newS = x.fi - t*get(newy, newx) + t*get(loc.se, loc.fi);
if(Hfind(newS) == -1){
Hinsert(newS, ++tot);
pa.push_back(mp(Hfind(x.fi), i));
Q.push(mp(newS, x.se+1));
Qxy.push(mp(newx, newy));
}
}
}
cin>>n;
while(n--){
LL state = 0;
for(int i = 0; i < 9; i++) cin>>x, state = state*10 + x;
if(Hfind(state) != -1){
x = Hfind(state);
while(x != 0){
cout<<ch[pa[x].se];
x = pa[x].fi;
}
cout<<endl;
} else cout<<"unsolvable"<<endl;
}
}
F题
矩阵优化问题
考虑由递推式构造一个线性变换矩阵
a[i] = p*a[i-1] + (q-p)*a[i-2] + m*i^c
把i^c看成b[i]
因为c小于等于2， 那么线性变换矩阵就A可以这样构造
1 1 1
0 1 2
0 0 1
这个矩阵乘i次后，A[0][0] = 1, A[1][1] = i, A[2][2] = i^2
然后和a[i]的递推式合在一起
就是1 1 1 0 0
0 1 2 0 0
0 0 1 0 0
0 0 0 0 q-p
0 0 0 1 p
只需要在A[c][4]的位置填上m就可以了
最后A自乘(n-3)次，与行向量(1, 3, 9, a1, a2)乘起来就是答案
矩阵可以进行快速幂，所以复杂度是O(logn)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MOD = 10007;
int Mn = 5;
typedef long long LL;
struct Matrix{
LL mat[10][10];
Matrix() { memset(mat, 0, sizeof(mat)); }
Matrix operator *(const Matrix &B) const{
Matrix ans;
for(int i = 0; i < Mn; i++){
for(int j = 0; j < Mn; j++){
LL temp = 0;
for(int k = 0; k < Mn; k++)
(temp += mat[i][k]*B.mat[k][j]) %= MOD;
ans.mat[i][j] = (temp + MOD) % MOD;
}
}
return ans;
}
void print(){
for(int i = 0; i < Mn; i++){
for(int j = 0; j < Mn; j++)
cout<<mat[i][j]<<" ";
cout<<endl;
}
}
}A;
Matrix powmod(Matrix A, int b){
Matrix ans;
for(int i = 0; i < Mn; i++) ans.mat[i][i] = 1;
for(; b; b >>= 1, A = A*A) if(b&1) ans = ans*A;
return ans;
}
int a1, a2, p, q, m, c, n;
int main(){
cin>>a1>>a2>>p>>q>>m>>c>>n;
if(n == 1) { cout<<a1<<endl; return 0; }
if(n == 2) { cout<<a2<<endl; return 0; }
A.mat[0][0] = A.mat[1][1] = A.mat[2][2] = A.mat[4][3] = 1;
A.mat[4][4] = p; A.mat[3][4] = q-p;
A.mat[0][2] = 1; A.mat[0][1] = 1;
A.mat[1][2] = 2;
A.mat[c][4] = m;
A = powmod(A, n-2);
LL a[5] = {1, 3, 9, a1, a2}, ans = 0;
for(int i = 0; i < 5; i++) (ans += A.mat[i][4]*a[i]) %= MOD;
cout<<ans<<endl;
}
G 题
离线莫队算法
将询问分块，使得普通暴力的时间也能在n*sqrt(n)的时间内跑完
可以自行搜索莫队算法，算是模板题了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
const int maxn = 50050;
int a[maxn], b[maxn], numa[maxn], numb[maxn], va[maxn], vb[maxn], ANS[maxn];
int ans, n, m, k, x, y;
struct Data{
int l, r, id, rank;
bool operator <(const Data& B) const{
return rank == B.rank ? r < B.r : rank < B.rank;
}
};
vector<Data> Q;
inline void Insert(int x){
int aa = a[x]^numa[a[x]], bb = b[x]^numb[b[x]];
ans -= numa[a[x]]*vb[aa^k];
ans -= va[bb^k]*numb[b[x]];
if((aa^k) == bb) ans += numa[a[x]]*numb[b[x]];
va[aa] -= numa[a[x]]; vb[bb] -= numb[b[x]];
numa[a[x]]++; numb[b[x]]++;
aa = a[x]^numa[a[x]], bb = b[x]^numb[b[x]];
va[aa] += numa[a[x]]; vb[bb] += numb[b[x]];
ans += numa[a[x]]*vb[aa^k];
ans += va[bb^k]*numb[b[x]];
if((aa^k) == bb) ans -= numa[a[x]]*numb[b[x]];
}
inline void Erase(int x){
int aa = a[x]^numa[a[x]], bb = b[x]^numb[b[x]];
ans -= numa[a[x]]*vb[aa^k];
ans -= va[bb^k]*numb[b[x]];
if((aa^k) == bb) ans += numa[a[x]]*numb[b[x]];
va[aa] -= numa[a[x]]; vb[bb] -= numb[b[x]];
numa[a[x]]--; numb[b[x]]--;
aa = a[x]^numa[a[x]], bb = b[x]^numb[b[x]];
va[aa] += numa[a[x]]; vb[bb] += numb[b[x]];
ans += numa[a[x]]*vb[aa^k];
ans += va[bb^k]*numb[b[x]];
if((aa^k) == bb) ans -= numa[a[x]]*numb[b[x]];
}
int main(){
cin>>n>>m>>k;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
int len = sqrt(m+0.5);
for(int i = 1; i <= m; i++){
scanf("%d %d", &x, &y);
Q.pb((Data){x, y, i, x/len});
}
sort(Q.begin(), Q.end());
int l = Q[0].l, r = Q[0].r; ans = 0;
for(int i = l; i <= r; i++) Insert(i);
ANS[Q[0].id] = ans;
for(int i = 1; i < Q.size(); i++){
while(l > Q[i].l) Insert(--l);
while(r < Q[i].r) Insert(++r);
while(l < Q[i].l) Erase(l++);
while(r > Q[i].r) Erase(r--);
ANS[Q[i].id] = ans;
}
for(int i = 1; i <= m; i++) printf("%d\n", ANS[i]);
}
H 题
模拟题
注意给出的时间不一定是排好序的
用队列模拟进出站的情况
然后如果不够，就加一列火车
最后输出答案即可
（我这里直接用了平衡树(set)，复杂度优化一个n，变成nlogn)
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> PII;
struct Data{
PII t;
int type;
bool operator <(const Data &B) const{
return (t == B.t) ? type < B.type : t < B.t;
}
};
vector<Data> data;
PII add(PII A, int B){
PII temp;
temp.fi = (A.se+B)/60 + A.fi;
temp.se = (A.se+B)%60;
return temp;
}
int T, D, na, nb, x, y, ansa, ansb;
char ch;
set<PII> Sa, Sb;
int main(){
cin>>T;
while(T--){
ansa = ansb = 0;
data.clear();
Sa.clear(); Sb.clear();
cin>>D;
cin>>na>>nb;
for(int i = 0; i < na; i++) {
cin>>x; cin>>ch; cin>>y;
data.pb((Data){mp(x, y), 1});
cin>>x; cin>>ch; cin>>y;
Sb.insert(add(mp(x, y), D));
}
for(int i = 0; i < nb; i++){
cin>>x; cin>>ch; cin>>y;
data.pb((Data){mp(x, y), 2});
cin>>x; cin>>ch; cin>>y;
Sa.insert(add(mp(x, y), D));
}
sort(data.begin(), data.end());
for(int i = 0; i < data.size(); i++){
if(data[i].type == 1){
if(Sa.empty()){
Sa.insert(mp(0, 0));
ansa++;
}
if(*Sa.begin() > data[i].t){
Sa.insert(mp(0, 0));
ansa++;
}
Sa.erase(*Sa.begin());
} else{
if(Sb.empty()){
Sb.insert(mp(0, 0));
ansb++;
}
if(*Sb.begin() > data[i].t){
Sb.insert(mp(0, 0));
ansb++;
}
Sb.erase(*Sb.begin());
}
}
cout<<ansa<<" "<<ansb<<endl;
}
}
I 题
数据结构
维护一个二进制串的字典树即可
每次枚举两个数相加，然后在字典树中删除这2个数，再进行xor查找
查找之后，再把这两个数加回去
复杂度是O(n^2logv)
（顺便暴力n^3+黑科技或许也能过）
#include <iostream>
#include <cstdio>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int maxn = 1010;
PII node[maxn*100];
int G[maxn*100][2];
int tot, n;
LL Pow[50], a[maxn];
void Insert(LL v){
//fi = 0 se = 1
int x = 0;
for(int i = 0; i <= 31; i++){
LL k = (v&Pow[31-i]) > 0 ? 1 : 0;
G[x][k]++;
if(k){
if(node[x].se == 0) node[x].se = ++tot;
x = node[x].se;
} else{
if(node[x].fi == 0) node[x].fi = ++tot;
x = node[x].fi;
}
}
}
void Erase(LL v){
int x = 0;
for(int i = 0; i <= 31; i++){
LL k = (v&Pow[31-i]) > 0 ? 1 : 0;
G[x][k]--;
x = k ? node[x].se : node[x].fi;
}
}
LL Find(LL v){
int x = 0;
LL ans = 0;
for(int i = 0; i <= 31; i++){
LL k = (v&Pow[31-i]) > 0 ? 0 : 1;
if(G[x][k]){
ans += Pow[31-i];
x = k ? node[x].se : node[x].fi;
} else {
x = k ? node[x].fi : node[x].se;
}
}
return ans;
}
int main(){
Pow[0] = 1;
for(int i = 1; i <= 31; i++) Pow[i] = Pow[i-1]*2;
cin>>n;
for(int i = 0; i < n; i++) cin>>a[i], Insert(a[i]);
LL ans = 0;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
Erase(a[i]); Erase(a[j]);
ans = max(ans, Find(a[i]+a[j]));
Insert(a[i]); Insert(a[j]);
}
}
cout<<ans<<endl;
}
J 题
排列组合
orz 好像没什么好说的
注意一些特殊情况就行
#include <iostream>
#include <cstdio>
using namespace std;
int a[3], H1[3][10000], H2[3][10000], n;
int main(){
cin>>n;
for(int i = 0; i < 3; i++) cin>>a[i];
for(int i = 0; i < 3; i++){
for(int j = -2; j <= 2; j++)
H1[i][((a[i]+j)%n+n)%n] = 1;
}
for(int i = 0; i < 3; i++) cin>>a[i];
for(int i = 0; i < 3; i++){
for(int j = -2; j <= 2; j++)
H2[i][((a[i]+j)%n+n)%n] = 1;
}
int ans1, ans2, ans3, t1, t2, t3;
ans1 = ans2 = ans3 = 1;
for(int i = 0; i < 3; i++){
t1 = t2 = t3 = 0;
for(int j = 0; j < n; j++){
if(H1[i][j]) t1++;
if(H2[i][j]) t2++;
if(H1[i][j] && H2[i][j]) t3++;
}
ans1 *= t1;
ans2 *= t2;
ans3 *= t3;
//cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;
}
cout<<ans1+ans2-ans3<<endl;
}