喵哈哈村的古怪石碑（一）
题解：暴力check一下是等比数列还是等差数列，然后输出答案即可。注意如果数据范围是1e9的话，就要快速幂了。
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
//#define LOCAL
const int N=100+10;
const int MOD=100007;
using namespace std;
long long a1,a2,a3,n,an;
void init(){
}
void dc(){
long long d=a2-a1;
an=a1+d*(n-1);
printf("%lld\n",an%MOD);
}
long long pow(long long a,long long b){
if (b==0) return 1;
if (b==1) return a%MOD;
long long tmp=pow(a,b/2);
if (b%2==0) return (tmp*tmp)%MOD;
else return ((tmp*tmp)%MOD*a)%MOD;
}
void db(){
long long q=a2/a1;
an=a1*pow(q,n-1);
printf("%lld\n",an%MOD);
}
int main(){
while(scanf("%lld%lld%lld%lld",&a1,&a2,&a3,&n)!=EOF){
if (a1!=1 || (a1==1 && a2-a1==a3-a2)) dc();
else db();
}
return 0;
}
喵哈哈村的古怪石碑（二）
题解：题目翻译过来，其实就是动态求全局第k大。小数据就直接暴力找第k大就好了。大数据你可以分块，也可以写个平衡树。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<ctime>
#include<queue>
#include<vector>
using namespace std;
#define clr(f,x) memset(f,x,sizeof f)
#define rep(it,a,b) for(int it=a;it<=b;++it)
#define _rep(it,a,b) for(int it=a;it>=b;--it)
#define vrep(it,a) for(int it=a;it--;)
#define PII pair<int,int>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define LL long long
const int maxn=20010;
int n;
int f[maxn],l[maxn],r[maxn],sz[maxn],v[maxn];
int root,tt;
inline void update(int x){
sz[x]=(l[x]>0)*sz[l[x]]+(r[x]>0)*sz[r[x]]+1;
}
inline void lt(int x){
int y=f[x],z=f[y];
f[x]=z;
if(z)l[z]==y?l[z]=x:r[z]=x;
f[r[y]=l[x]]=y;
f[l[x]=y]=x;
update(y);
}
inline void rt(int x){
int y=f[x],z=f[y];
f[x]=z;
if(z)l[z]==y?l[z]=x:r[z]=x;
f[l[y]=r[x]]=y;
f[r[x]=y]=x;
update(y);
}
inline void splay(int x){
while(f[x]){
int y=f[x],z=f[y];
if(!z){l[y]==x?rt(x):lt(x);break;}
if(l[z]==y)
if(l[y]==x)rt(y),rt(x);
else lt(x),rt(x);
if(r[z]==y)
if(r[y]==x)lt(y),lt(x);
else rt(x),lt(x);
}
update(x);
root=x;
}
inline int rk(int x){
int y=root;
while(1){
if(sz[l[y]]+1==x)return y;
if(sz[l[y]]<x){
x-=sz[l[y]]+1;
y=r[y];
}else y=l[y];
}
}
inline void del(int x){
splay(x);
if(r[x]==0){
f[root=l[x]]=0;
return;
}
int y=r[x];
f[y]=0;
while(l[y])y=l[y];
f[l[y]=l[x]]=y;
splay(l[x]);
}
inline void ins(int &x,int y){
if(!x){
v[x=++tt]=y;
return;
}
if(y>=v[x])ins(r[x],y),f[r[x]]=x;
else ins(l[x],y),f[l[x]]=x;
}
inline void work(){
scanf("%d",&n);
int x,y,z;
tt=0;
LL total=0;
int ans=0;
rep(i,1,n){
scanf("%d%d",&x,&y);
if(!x){
total+=y;
ins(root,y);
splay(tt);
}else{
z=rk(sz[root]-y+1);
ans^=v[z];
if((LL)v[z]*sz[root]<=total){
total+=v[z];
ins(root,v[z]);
splay(tt);
}else{
total-=v[z];
del(z);
}
}
}
printf("%d\n",ans);
}
int main(){
work();
return 0;
}
喵哈哈村的古怪石碑（三）
题解：实际上翻译过来就是求最大生成树，这个和求最小生成树是一样的，我们还是用克鲁斯卡尔来做就好了。
代码：
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
const double eps = 1e-10;
const int INF = ~0U>>1;
using namespace std;
int n, nes, sg;
int ap[5010], bp[5010];
int f[5010];
double ans;
struct quk
{
double dis;
int a, b;
} e[12502510];
struct point
{
double x, y;
} p[5010];
double dist(point a, point b)
{
return (a.x * b.x + a.y * b.y + abs(a.x - b.x) + abs(a.y - b.y) + sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))) / 3;
}
int father(int u)
{
return f[u] == u ? u : f[u] = father(f[u]);
}
bool marge(int p)
{
int u = father(e[p].a), v = father(e[p].b);
if (u == v) return false;
ap[++nes] = e[p].a; bp[nes] = e[p].b; ans += e[p].dis;
f[u] = v;
return true;
}
bool cmp(const quk &a, const quk &b)
{
return a.dis > b.dis;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf %lf", &p[i].x, &p[i].y), f[i] = i;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
e[++sg].dis = dist(p[i], p[j]), e[sg].a = i, e[sg].b = j;
sort(e + 1, e + sg + 1, cmp);
int nop = 0;
for (int i = 1; i < n; ++i)
while (!marge(++nop));
printf("%.4f\n", ans);
}
喵哈哈村的奇怪石碑（四）
题解：实际上是模拟题，我们对于每一个基因，我们都能够分析出概率是多少，然后所有的乘起来，再化简就好了。
但是这道题要高精度，注意~
代码：
#include <iostream>
using namespace std;
const int max_num = 100000000l;
typedef struct { bool flag; int cnt2, cnt3; } Cell;
typedef struct { Cell unisex[2] , gene[6][3]; } Table;
typedef struct { int len, num[80];} Gjd;
class Node
{
Table genotype[4];
void makenum();
void makelist();
public:
int ans2, ans3;
Gjd num2[2081], num3[2081];
void init() { makenum(); makelist(); }
void reclear() { ans2 = ans3 = 0; }
bool calc(int x, int y, int z)
{
if(z >= 4)
{
z -= 4;
if(!genotype[x].unisex[z].flag) return false;
ans2 += genotype[x].unisex[z].cnt2;
ans3 += genotype[x].unisex[z].cnt3;
}
else
{
if(!genotype[x].gene[y][z].flag) return false;
ans2 += genotype[x].gene[y][z].cnt2;
ans3 += genotype[x].gene[y][z].cnt3;
}
return true;
}
} You;
ostream& operator << (ostream &out, const Gjd &x)
{
int i = x.len - 1;
out << x.num[i];
while(i--) out.width(8), out << x.num[i];
return out;
}
int main()
{
int T, n;
string ma, fa, me;
ios::sync_with_stdio(false);
cin >> T;
if(T <= 0 || T > 20) return 1;
cout.fill('0');
You.init();
while(T--)
{
cin >> n >> ma >> fa >> me;
if(n <= 0 || n > 520 || (int)ma.length() != n || (int)fa.length() != n || (int)me.length() != n) return 1;
You.reclear();
while(n--)
{
if(me[n] == '3' || (me[n] >= '4' && !((ma[n] < '4') ^ (fa[n] < '4')))) return 1;
if(ma[n] <= fa[n])
{ if(!You.calc((int)ma[n] - '0', (int)fa[n] - '0', (int)me[n] - '0')) break; }
else if(!You.calc((int)fa[n] - '0', (int)ma[n] - '0', (int)me[n] - '0')) break;
}
if(n >= 0) cout << "0/0" << endl;
else cout << You.num3[You.ans3] << "/" << You.num2[You.ans2] << endl;
}
return 0;
}
void Node::makenum()
{
int i, j;
num2[0].len = num2[0].num[0] = num3[0].len = num3[0].num[0] = 1;
for(i = 1; i <= 2080; ++i)
{
num2[i].len = num2[i - 1].len;
for(j = 0; j < num2[i].len; ++j)
{
num2[i].num[j] += num2[i - 1].num[j] << 1;
if(num2[i].num[j] >= max_num)
{
num2[i].num[j + 1] += num2[i].num[j] / max_num;
num2[i].num[j] %= max_num;
}
}
if(num2[i].num[num2[i].len]) ++num2[i].len;
num3[i].len = num3[i - 1].len;
for(j = 0; j < num3[i].len; ++j)
{
num3[i].num[j] += num3[i - 1].num[j] * 3;
if(num3[i].num[j] >= max_num)
{
num3[i].num[j + 1] += num3[i].num[j] / max_num;
num3[i].num[j] %= max_num;
}
}
if(num3[i].num[num3[i].len]) ++num3[i].len;
}
}
void Node::makelist()
{
//unisex
genotype[0].unisex[0].flag = true;
genotype[1].unisex[0].flag = genotype[1].unisex[1].flag = true;
genotype[1].unisex[0].cnt2 = genotype[1].unisex[1].cnt2 = 1;
genotype[2].unisex[1].flag = true;
genotype[3].unisex[0].flag = genotype[3].unisex[1].flag = true;
genotype[3].unisex[0].cnt2 = genotype[3].unisex[1].cnt2 = 2;
genotype[3].unisex[0].cnt3 = 1;
//gene
genotype[0].gene[0][0].flag = true;
genotype[0].gene[1][0].flag = genotype[0].gene[1][1].flag = true;
genotype[0].gene[1][0].cnt2 = genotype[0].gene[1][1].cnt2 = 1;
genotype[0].gene[2][1].flag = true;
genotype[0].gene[3][0].flag = genotype[0].gene[3][1].flag = true;
genotype[0].gene[3][0].cnt2 = genotype[0].gene[3][1].cnt2 = 2;
genotype[0].gene[3][0].cnt3 = 1;
genotype[0].gene[4][0].flag = true;
genotype[0].gene[5][1].flag = true;
genotype[1].gene[1][0].flag = genotype[1].gene[1][1].flag = genotype[1].gene[1][2].flag = true;
genotype[1].gene[1][0].cnt2 = genotype[1].gene[1][2].cnt2 = 2;
genotype[1].gene[1][1].cnt2 = 1;
genotype[1].gene[2][1].flag = genotype[1].gene[2][2].flag = true;
genotype[1].gene[2][1].cnt2 = genotype[1].gene[2][2].cnt2 = 1;
genotype[1].gene[3][0].flag = genotype[1].gene[3][1].flag = genotype[1].gene[3][2].flag = true;
genotype[1].gene[3][0].cnt2 = genotype[1].gene[3][2].cnt2 = 3;
genotype[1].gene[3][1].cnt2 = 1;
genotype[1].gene[3][0].cnt3 = 1;
genotype[1].gene[4][0].flag = genotype[1].gene[4][1].flag = true;
genotype[1].gene[4][0].cnt2 = genotype[1].gene[4][1].cnt2 = 1;
genotype[1].gene[5][1].flag = genotype[1].gene[5][2].flag = true;
genotype[1].gene[5][1].cnt2 = genotype[1].gene[5][2].cnt2 = 1;
genotype[2].gene[2][2].flag = true;
genotype[2].gene[3][1].flag = genotype[2].gene[3][2].flag = true;
genotype[2].gene[3][1].cnt2 = genotype[2].gene[3][2].cnt2 = 2;
genotype[2].gene[3][1].cnt3 = 1;
genotype[2].gene[4][1].flag = true;
genotype[2].gene[5][2].flag = true;
genotype[3].gene[3][0].flag = genotype[3].gene[3][1].flag = genotype[3].gene[3][2].flag = true;
genotype[3].gene[3][0].cnt2 = genotype[3].gene[3][2].cnt2 = 4;
genotype[3].gene[3][1].cnt2 = 3;
genotype[3].gene[3][0].cnt3 = 2;
genotype[3].gene[3][1].cnt3 = 1;
genotype[3].gene[4][0].flag = genotype[3].gene[4][1].flag = true;
genotype[3].gene[4][0].cnt2 = genotype[3].gene[4][1].cnt2 = 2;
genotype[3].gene[4][0].cnt3 = 1;
genotype[3].gene[5][1].flag = genotype[3].gene[5][2].flag = true;
genotype[3].gene[5][1].cnt2 = genotype[3].gene[5][2].cnt2 = 2;
genotype[3].gene[5][1].cnt3 = 1;
}