一道题开一篇文章实在浪费，于是决定以后零零散散做的题就放在这个集子里了。如果数量过多会考虑再开。
JSOI2004 平衡点（模拟退火）
提交入口
https://www.luogu.com.cn/problem/P1337
题目描述
如图，有 $n$ 个重物，每个重物系在一条足够长的绳子上。
每条绳子自上而下穿过桌面上的洞，然后系在一起。图中 $x$ 处就是公共的绳结。假设绳子是完全弹性的（即不会造成能量损失），桌子足够高（重物不会垂到地上），且忽略所有的摩擦，求绳结 $x$ 最终平衡于何处。
注意：桌面上的洞都比绳结 $x$ 小得多，所以即使某个重物特别重，绳结 $x$ 也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。
输入格式
文件的第一行为一个正整数 $n$（$1\le n\le 1000$），表示重物和洞的数目。
接下来的 $n$ 行，每行是 $3$ 个整数 $x_i, y_i, w_i$，分别表示第 $i$ 个洞的坐标以及第 $i$ 个重物的重量。（$-10000\le x_i,y_i\le10000, 0<w_i\le1000$）
输出格式
你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结 $x$ 的横坐标和纵坐标。两个数以一个空格隔开。
样例输入 #1
3
0 0 1
0 2 1
1 1 1样例输出 #1
0.577 1.000分析
待续。先贴代码。
#include <bits/stdc++.h>
using namespace std;
const int MAXN =1e4+10;
int n,g[MAXN];
double minlen=DBL_MAX;
struct Point{
double x, y;
Point(double a=0.0, double b=0.0):x(a),y(b){}
}P[MAXN];
Point ans;
inline double Sqr(double x){return x*x;}
inline double Rand(){
return double(rand())/double(RAND_MAX);
}
inline double dis(Point a,Point b){
return sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y));
}
bool accept(double delta,double temp){
return delta<0||Rand()<exp(-delta/temp);
}
double calc(Point origin){
double len=0;
for(int i=0;i<n;i++)
len+=dis(origin,P[i])*g[i];
if(len<minlen){
ans=origin;
minlen=len;
}
return len;
}
void SA(Point ans0,double T0,double dec,double end){
double temp=T0;
Point nowpos=ans0;
double nowlen=calc(nowpos);
while(temp>end){
Point nextpos=Point(nowpos.x+temp*(Rand()*2-1),nowpos.y+temp*(Rand()*2-1));
double nlen=calc(nextpos);
if(accept(nlen-nowlen,temp)){
nowpos=nextpos;
nowlen=nlen;
}
temp*=dec; //dec为退火系数
}
for(int i=0;i<1000;i++){ //精度维护
Point rnd=Point(ans.x+temp*(Rand()*2-1),ans.y+temp*(Rand()*2-1));
calc(rnd);
}
}
int main(){
scanf("%d",&n);
Point init;
for(int i=0;i<n;i++){
scanf("%lf%lf%d",&P[i].x,&P[i].y,&g[i]);
init.x+=P[i].x;
init.y+=P[i].y;
}
init.x/=n;
init.y/=n;
SA(init,1e5,1-1e-2,1e-3);
printf("%.3f %.3f\n",ans.x,ans.y);
return 0;
}有机化学之神偶尔会做作弊（tarjan, lca）
提交入口
https://www.luogu.com.cn/problem/P2783
题意简述
给你一个 $n$ 个点，$m$ 条边的无向图。把图中所有的环变为一个点，求变化后某两个点之间有多少个点。
输入格式
第一行两个整数 $n$，$m$。表示有 $n$ 个点，$m$ 根键。
接下来 $m$ 行每行两个整数 $u$，$v$ 表示 $u$ 号碳和 $v$ 号碳有一根键。
接下来一个整数 $tot$ 表示询问次数。
接下来 $tot$ 行每行两个整数，$a$，$b$ 表示询问的两个碳的编号。
输出格式
共 $tot$ 行，每行一个二进制数，表示答案。
样例输入 #1
3 2
1 2
2 3
2
1 2
2 3样例输出 #1
10
10提示
两个碳不成环。
数据范围及约定
对于 $100\%$ 的数据，$1<n\le10 ^ 4$，$1<m\le5\times 10 ^ 4$。
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn=1e4+3;
const int maxm=1e5+3;
// Edge_number in a general graph is twice that of a one-way graph
struct Edge{int v,next;};
Edge edge[maxm],edge2[maxm];
int head[maxn],dfn[maxn],low[maxn],stac[maxn],color[maxn],fa[maxn];
int n,m,tot,num,top,cnt,tot_in_txt,lcafa[maxn][25];
int head2[maxn],tot2,dep[maxn],max0;
bool ins[maxn], vis[maxn];
const int topow[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192};
inline void rd(int &x){
int w=x=0;
char ch=0;
while(ch<'0'||'9'<ch) w|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=w?-x:x;
}
inline void addedge(int x,int y){
edge[++tot].v=y;
edge[tot].next=head[x];
head[x]=tot;
}
inline void addedge2(int x,int y){
edge2[++tot2].v=y;
edge2[tot2].next=head2[x];
head2[x]=tot2;
}
void tarjan(int x){
low[x]=dfn[x]=++num;
stac[++top]=x; ins[x]=true;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].v;
if(!dfn[y]){
fa[y]=x;
tarjan(y);
low[x]=MIN(low[x],low[y]);
}
else if(ins[y] && y!=fa[x]){
low[x]=MIN(low[x],dfn[y]);
}
}
if(dfn[x]==low[x]){
++cnt; int y;
do{
y=stac[top--]; ins[y]=false;
color[y]=cnt;
}while(x!=y);
}
}
void lcainit(int x){
vis[x] = true;
for(int i=1;i<=max0;i++)
if(lcafa[x][i-1])lcafa[x][i]=lcafa[lcafa[x][i-1]][i-1];
else break;
for(int i=head2[x];i;i=edge2[i].next){
int y=edge2[i].v;
if(y!=lcafa[x][0]){
lcafa[y][0]=x;
dep[y]=dep[x]+1;
if(!vis[y]) lcainit(y);
}
}
}
inline int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int delta=dep[u]-dep[v];
for(int x=0;x<=max0;x++)
if((1<<x)&delta)u=lcafa[u][x];
if(u==v)return u;
for(int x=max0;x>=0;x--)
if(lcafa[u][x]!=lcafa[v][x]){
u=lcafa[u][x];
v=lcafa[v][x];
}
return lcafa[u][0];
}
int main(){
rd(n); rd(m);
for(int i=1;i<=m;i++){
int x,y;
rd(x); rd(y);
addedge(x,y);
addedge(y,x);
}
rd(tot_in_txt);
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int x=1;x<=n;x++){
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].v;
if(color[x]!=color[y]){
addedge2(color[x], color[y]);
addedge2(color[y], color[x]);
}
}
}
max0=(int)(log(cnt)/log(2))+3;
lcainit(1);
while(tot_in_txt--){
int a,b;
rd(a); rd(b);
int k = lca(color[a], color[b]);
int temp = dep[color[a]] + dep[color[b]] - (dep[k]<<1) + 1;
char ans[15] = "00000000000000";
for(int i=13; ~i; i--){
if(temp>=topow[i]){
ans[13-i] = '1';
temp -= topow[i];
}
}
int i = 0;
while(ans[i]=='0') i++;
for(; i<=13; i++)putchar(ans[i]);
putchar('\n');
}
return 0;
}yLOI2022 枕万梦（排序）
提交入口
https://www.luogu.com.cn/problem/P9472
题目描述
天亮了，扶苏不敌困意，早早地进入了梦乡。在失去引力的梦里，扶苏遇到了好多串漂浮着的数列，它们的长度都相等，而且都是美妙的等比数列！出于本能，扶苏想要把这些数列按照字典序排序，可是在梦里扶苏失去了思考的能力，请你来帮帮她！
具体地，有 $n$ 个编号从 $1$ 到 $n$ 的数列 $a_1, a_2, \dots a_n$，每个数列的长度均为 $m + 1$。第 $i$ 个数列 $a_i$ 满足递推式 $a_{i,j} = a_{i,j - 1} \times i$，其中 $1 \leq j \leq m$。而扶苏会告诉你每个序列的首项 $a_{i,0}$，你需要帮助她把这些数列按字典序排序。
输入格式
输入的第一行是两个整数，依次表示 $n$ 和 $m$。
接下来 $n$ 行，每行一个整数，第 $i$ 行的整数表示数列 $a_i$ 的首项 $a_{i,0}$。
输出格式
输出一行 $n$ 个整数，第 $i$ 个整数表示字典序第 $i$ 小的数列的编号。
样例 #1
样例输入 #1
2 2
1
2样例输出 #1
1 2样例 #2
样例输入 #2
2 3
1
-1样例输出 #2
2 1样例 #3
样例输入 #3
2 2
1
1样例输出 #3
1 2样例 #4
样例输入 #4
见附加文件中的 B4.in样例输出 #4
见附加文件中的 B4.ans提示
样例 1 解释
共有两个数列，每个数列的长度均为 $2+1=3$。
对第一个数列 $a_1$：
- 已知其首项 $a_{1,0} = 1$。
- 根据 $a_{i,j} = a_{i,j - 1} \times i$，取 $i=1,j = 1$ 可以得到 $a_{1,1} = a_{1,0} \times 1 = 1$。
- 根据 $a_{i,j} = a_{i,j - 1} \times i$，取 $i=1,j = 2$ 可以得到 $a_{1,2} = a_{1,1} \times 1= 1$。
所以数列 $a_1$ 是 $1,1,1$。
对第二个数列 $a_2$：
- 已知其首项 $a_{2,0} = 2$。
- 根据 $a_{i,j} = a_{i,j - 1} \times i$，取 $i=2,j = 1$ 可以得到 $a_{2,1} = a_{2,0} \times 2 = 2 \times 2 = 4$。
- 根据 $a_{i,j} = a_{i,j - 1} \times i$，取 $i=2,j = 2$ 可以得到 $a_{2,2} = a_{2,1} \times 2= 4 \times 2 = 8$。
所以数列 $a_2$ 是 $2,4,8$。
比较字典序可得数列 $a_1$ 是字典序最小的数列。所以输出 $1$。
样例 2 解释
数列 $a_1$ 为 $1,1,1,1$，数列 $a_2$ 为 $-1, -2,-4,-8$。
数据规模与约定 本题共 $10$ 个测试点，各测试点信息如下表：
特殊约定 A：保证 $a_{i,0}$ 均相等。
特殊约定 B：保证 $a_{i,0}$ 互不相等。
对全部的测试点，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 10^9$，$1 \leq |a_{i,0}| \leq 10^9$。
提示
对两个数列 $a_i, a_j$，按如下方式比较其字典序：
找到最小的满足 $a_{i,p} \neq a_{j, p}$ 的下标 $p$，比较 $a_{i, p}$ 和 $a_{j, p}$ 的大小：
- 如果 $a_{i,p} < a_{j, p}$，则称 $a_i$ 的字典序比 $a_j$ 的小。
- 如果 $a_{i,p} > a_{j, p}$，则称 $a_i$ 的字典序比 $a_j$ 的大。
可以证明，在本题的限制下，这样的 $p$ 一定存在。
分析
要求根据字典序排序。若两个数列第一个元素就不等，便可比较大小；若两个数列第一个元素相等，由数列定义，第二个元素必然不等，于是可比较大小。对于首元素为零的数列，整个数列都是零。由此得到下述做法：
对于两个不等的 $a_{i,0}$ , 升序排序。对于两个相等的 $a_{i,0}$ , 分正负两种情况：若 $a_{i,0}>0$ , 则行数越大，位序靠后；若 $a_{i,0}<0$ , 则行数越大，位序靠前。
#include <algorithm>
#include <cstdio>
using LL = long long;
using namespace std;
LL n,m;
struct mnode{
LL mcontent;
LL mindex;
bool operator < (const mnode& v)const{
if(mcontent != v.mcontent)
return mcontent < v.mcontent;
else
if(mcontent > 0)
return mindex < v.mindex;
else
return mindex > v.mindex;
}
}marray[100010];
int main(){
scanf("%lld%lld",&n,&m);
for(LL i=1; i<=n; i++){
LL x;
scanf("%lld",&x);
marray[i].mcontent = x;
marray[i].mindex = i;
}
sort(marray+1, marray+1+n);
for(LL i=1; i<=n; i++){
printf("%lld ",marray[i].mindex);
}
return 0;
}平衡二叉树
最近考研应试之余，尝试着用王道的思路手写了平衡二叉树的代码，但是没有完成，只是个半成品。如果之后还记得的话，也许我会完成它？
#include <cstdio>
#define MAX(a,b) ((a)>(b)?(a):(b))
inline void rd(int &x){
int w=x=0;
char ch=0;
while(ch<'0'||'9'<ch) w|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=w?-x:x;
}
struct avlNode{
int value;
int cnt;
int lsub_h; //left sub_tree's height
int rsub_h;
int lsub_num; //size of leftSubtree, excluding itself
int rsub_num;
avlNode *lchild, *rchild, *fa;
};
class avlTree{
public:
avlTree(){ T = nullptr; }
avlNode* getRoot(){ return T; }
void insertX(avlNode*& K, int x){
avlNode* p = bstInsert(K, x, nullptr);
maintain_balance_insert(p);
}
void deleteX(int x){ // assume there is x
avlNode* p = find_X_delete(T, x);
p->cnt--;
if(p->cnt>=1)return;
if(p->lchild==nullptr&&p->rchild==nullptr){
if(p==p->fa->lchild)
p->fa->lchild = nullptr;
else
p->fa->rchild = nullptr;
}
else if(p->lchild!=nullptr&&p->rchild==nullptr){ // !
if(p==p->fa->lchild)
p->fa->lchild = p->lchild;
else
p->fa->rchild = p->lchild;
p->lchild->fa = p->fa;
}
else if(p->lchild==nullptr&&p->rchild!=nullptr){
if(p==p->fa->lchild)
p->fa->lchild = p->rchild;
else
p->fa->rchild = p->rchild;
p->rchild->fa = p->fa;
}
else {
avlNode* qwq = maxValue_in_lsubtree(p);
p->value = qwq->value;
p->cnt = qwq->cnt;
p = qwq;
if(p==p->fa->lchild)
p->fa->lchild = p->lchild;
else
p->fa->rchild = p->lchild;
p->lchild->fa = p->fa;
}
maintain_balance_delete(p);
delete p;
}
int index_X(int x){
//find an avlNode whose value is x，return its index
//at this point, the binary-tree is balanced
avlNode* p = find_X(T, x); // O(logN)
int ans = -1;
if(p==p->fa->rchild){
avlNode* G = find_left_daddy(p);
ans = G->lsub_num + G->rsub_num + G->cnt
- p->rsub_num - p->cnt + 1;
//+1: the value-x avlNode goes the end
}
else if(p==p->fa->lchild){
avlNode* G = find_right_daddy(p);
ans = G->fa->lsub_num + G->fa->cnt
+ p->lsub_num + 1;
}
if(ans==-1) printf("No such avlNode.\n");
return ans;
}
int findIndex_X(){
//Query the avlNode whose index is x, return its value
}
int preX(){}
int afterX(){}
private:
avlNode* find_X(avlNode* K, int x){
while(K!=nullptr && x!=K->value){
if(x<K->value) K=K->lchild;
else K=K->rchild;
}
if(K==nullptr)
printf("function find_X() failed.\n");
return K;
}
avlNode* find_X_delete(avlNode* K, int x){
while(K!=nullptr && x!=K->value){
if(x<K->value){
K->lsub_num--;
K=K->lchild;
}
else {
K->rsub_num--;
K=K->rchild;
}
}
if(K==nullptr)
printf("function find_X() failed.\n");
return K;
}
avlNode* find_left_daddy(avlNode* p){}
avlNode* find_right_daddy(avlNode* p){}
int lsubtree_height(avlNode* x){
if(x->lsub_h) return x->lsub_h;
if(x->lchild==nullptr){
x->lsub_h = 0;
return x->lsub_h;
}
x->lsub_h = MAX(lsubtree_height(x->lchild),
rsubtree_height(x->lchild))+ 1;
return x->lsub_h;
}
int rsubtree_height(avlNode* x){
if(x->rsub_h) return x->rsub_h;
if(x->rchild==nullptr){
x->rsub_h = 0;
return x->rsub_h;
}
x->rsub_h = MAX(lsubtree_height(x->rchild),
rsubtree_height(x->rchild))+ 1;
return x->rsub_h;
}
avlNode* find_Unbalanced_Node(avlNode* p){
int sub_balance = 0;
while(sub_balance>=-1&&sub_balance<=1){ //sub_balance = 0,1,-1
p = p->fa;
if(p==nullptr) return p;
p->lsub_h = p->rsub_h = 0; // erase old data
int lch = lsubtree_height(p);
int rch = rsubtree_height(p);
sub_balance = lch-rch;
}
return p;
}
avlNode* bstInsert(avlNode* K, int x, avlNode* myfa){
if(K==nullptr){
K = new avlNode;
K->value = x;
K->fa = myfa;
K->lchild = K->rchild = nullptr;
return K;
}
else if(x==K->value){
K->cnt++;
return K;
}
else if(x < K->value){
K->lsub_num++; // nice code <(ˉ^ˉ)>
bstInsert(K->lchild, x, K);
}
else{
K->rsub_num++;
bstInsert(K->rchild, x, K);
}
}
void maintain_balance_insert(avlNode* p){
avlNode* subroot = find_Unbalanced_Node(p);
// after find_Unbalanced_Node, lsub_h & rsub_h is updated
if(subroot->lchild->lsub_h==subroot->lchild->rsub_h+1){
rightRotation(subroot->lchild);
}
else if(subroot->rchild->lsub_h+1==subroot->rchild->rsub_h){
leftRotation(subroot->rchild);
}
else if(subroot->lchild->lsub_h+1==subroot->lchild->rsub_h){
leftRotation(subroot->lchild->rchild);
rightRotation(subroot->lchild);
}
else if(subroot->rchild->lsub_h==subroot->rchild->rsub_h+1){
rightRotation(subroot->rchild->lchild);
leftRotation(subroot->rchild);
}
}
void maintain_balance_delete(avlNode* p){
// 删除的节点向上计算 balance
avlNode* subroot = find_Unbalanced_Node(p);
if(subroot==nullptr) return;
// to do
}
void leftRotation(avlNode* p){
avlNode *f = p->fa, *gf = f->fa;
f->rchild = p->lchild;
f->rsub_num = p-> lsub_num;
f->rchild->fa = f;
p->lchild = f;
p->lsub_num = f->lsub_num + f->rsub_num + 1;
f->fa = p;
if(gf->lchild==f){
gf->lchild = p;
}
else if(gf->rchild==f){
gf->rchild = p;
}
p->fa = gf;
}
void rightRotation(avlNode* p){
avlNode *f = p->fa, *gf = f->fa;
f->lchild = p->rchild;
f->lsub_num = p-> rsub_num;
f->lchild->fa = f;
p->rchild = f;
p->rsub_num = f->lsub_num + f->rsub_num + 1;
f->fa = p;
if(gf->lchild==f){
gf->lchild = p;
}
else if(gf->rchild==f){
gf->rchild = p;
}
p->fa = gf;
}
avlNode* maxValue_in_lsubtree(avlNode* p){}
avlNode* T; // root
};
avlTree P3369;
int main(){
int n; rd(n);
avlNode* rooT = P3369.getRoot();
while(n--){
int opt, x;
rd(opt); rd(x);
switch(opt){
case 1: P3369.insertX(rooT, x); break;
case 2: P3369.deleteX(x); break;
case 3: printf("%d\n", P3369.index_X(x)); break;
case 4: printf("%d\n", P3369.findIndex_X()); break;
case 5: printf("%d\n", P3369.preX()); break;
case 6: printf("%d\n", P3369.afterX()); break;
}
}
return 0;
}5 倍经验日（背包）
题目背景
现在乐斗有活动了！每打一个人可以获得 5 倍经验！absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。
题目描述
现在 absi2011 拿出了 $x$ 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。
由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 $2$ 个药去打别人，别人却表明 $3$ 个药才能打过，那么相当于你输了并且这两个属性药浪费了。
现在有 $n$ 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。
要求求出最大经验 $s$，输出 $5s$。
输入格式
第一行两个数，$n$ 和 $x$。
后面 $n$ 行每行三个数，分别表示失败时获得的经验 $\mathit{lose}_i$，胜利时获得的经验 $\mathit{win}_i$ 和打过要至少使用的药数量 $\mathit{use}_i$。
输出格式
一个整数，最多获得的经验的五倍。
样例 #1
样例输入 #1
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2样例输出 #1
1060提示
【Hint】
五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。
【数据范围】
- 对于 $10\%$ 的数据，保证 $x=0$。
- 对于 $30\%$ 的数据，保证 $0\le n\le 10$，$0\le x\le 20$。
- 对于 $60\%$ 的数据，保证 $0\le n,x\le 100$， $10<lose_i,win_i\le 100$，$0\le use_i\le 5$。
- 对于 $100\%$ 的数据，保证 $0\le n,x\le 10^3$，$0<lose_i\le win_i\le 10^6$，$0\le use_i\le 10^3$。
【题目来源】
fight.pet.qq.com
absi2011 授权题目
分析
为防止学校自命题出 dp 埋伏一手，还是练两道为妙。
整体思路看起来比较显然，但是特判会有点麻烦。大佬们都是用数组的，我还是老老实实用记忆化搜索。
#include <cstdio>
#define MAX(a,b) ((a)>(b)?(a):(b))
const int MAXN = 1e3+5;
int f[MAXN][MAXN],lose[MAXN],win[MAXN],use[MAXN];
int dp(int n, int w){
if(n<=0) return 0;
if(f[n][w]) return f[n][w];
if(!use[n]){
f[n][w] = dp(n-1,w) + win[n];
return f[n][w];
}
if(!w){
f[n][w] = dp(n-1,0) + lose[n];
return f[n][w];
}
int temp1 = dp(n-1,w) + lose[n];
int temp2 = (w-use[n]>=0)?(dp(n-1,w-use[n]) + win[n]):0;
f[n][w] = MAX(temp1, temp2);
return f[n][w];
}
int main(){
int n, x;
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&lose[i],&win[i],&use[i]);
}
printf("%lld",5ll*dp(n,x));
return 0;
}杂记
# define MAX(a,b) ((a)>(b)?(a):(b))
# define MIN(a,b) ((a)<(b)?(a):(b))这个常见的宏定义有大问题，今天被我遇到了。 来看导致问题的代码：
alpha = MAX(alpha, alpha_beta(T, alpha, beta, false));在编译前，宏会把这行代码展开，它实际变成了：
alpha = ((alpha) > (alpha_beta(T, alpha, beta, false)) ? (alpha) : (alpha_beta(T, alpha, beta, false)));这个函数调用在展开后的代码里出现了两次！
永远不要将带有副作用或计算成本高昂的表达式（如函数调用）直接放在宏参数中。
后记
不再给出代码，仅给出链接。