CCF_NOI_wyz66 @ 2024-03-24 14:30:10
这道题能用DP做么
by GoodLuckCat @ 2024-03-24 14:36:43
你猜
by HenryQ2022 @ 2024-03-24 14:36:43
wyy，你觉得呢
by Alvis_F @ 2024-03-24 14:40:54
@CCF_NOI_wyz66 很多方法都可以做的，比如这个
by I_like_play_eggy @ 2024-03-31 11:51:06
@bca_
by h120316 @ 2024-04-06 13:40:34
求关
by Jacky0909 @ 2024-05-21 21:12:55
@bca_ 看看这个：
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <csignal>
#include <csetjmp>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <bits/c++config.h>
#include <bits/functexcept.h>
#include <bits/cpp_type_traits.h>
#include <ext/type_traits.h>
#include <ext/numeric_traits.h>
#include <bits/stl_pair.h>
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_iterator_base_funcs.h>
#include <bits/stl_iterator.h>
#include <bits/concept_check.h>
#include <debug/debug.h>
#include <bits/move.h>
using namespace std;
typedef long long ll;
const int GRAPHN = 3, AB = 200000000;
int w[GRAPHN+2][GRAPHN+2], d[GRAPHN+2], v[GRAPHN+2];
int read(){
int s = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)){
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int dfs(int x){
if(x <= 100) return x;
return dfs(x / 2) + dfs(x - x / 2);
}
int qmi(int m, int k, int p){
int res = 1 % p, t = m;
while(k){
if(k & 1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
void dijkstra(){
memset(d, 0x3f, sizeof(d));
memset(v, 0, sizeof(v));
d[1] = 0;
for(int i = 1; i < GRAPHN; i++){
int x = 0;
for(int j = 1; j <= GRAPHN; j++)
if(!v[j] && (x == 0 || d[j] < d[x])) x = j;
v[x] = 1;
for(int y = 1; y <= GRAPHN; y++)
d[y] = min(d[y], d[x] + w[x][y]);
}
}
queue<int> q;
void spfa(){
memset(d, 0x3f, sizeof(d));
memset(v, 0, sizeof(v));
d[1] = 0, v[1] = 1;
q.push(1);
while(q.size()){
int x = q.front(); q.pop();
v[x] = 0;
for(int i = 1; i <= GRAPHN; i++){
if(d[i] > d[x] + w[x][i]) {
d[i] = d[x] + w[x][i];
if(!v[i]) q.push(i), v[i] = 1;
}
}
}
}
struct node{
int data,rev,sum;
node *son[2],*pre;
bool judge();
bool isroot();
void pushdown();
void update();
void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x){
node *now=lct+ ++top;
now->data=x;
now->pre=now->son[1]=now->son[0]=lct;
now->sum=0;
now->rev=0;
return now;
}
bool node::judge(){
return pre->son[1]==this;
}
bool node::isroot(){
if(pre==lct)return true;
return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown(){
if(this==lct||!rev)return;
swap(son[0],son[1]);
son[0]->rev^=1;
son[1]->rev^=1;
rev=0;
}
void node::update(){
sum=son[1]->sum+son[0]->sum+data;
}
void node::setson(node *child,int lr){
this->pushdown();
child->pre=this;
son[lr]=child;
this->update();
}
void rotate(node *now){
node *father=now->pre,*grandfa=father->pre;
if(!father->isroot()) grandfa->pushdown();
father->pushdown();
now->pushdown();
int lr=now->judge();
father->setson(now->son[lr^1],lr);
if(father->isroot()) now->pre=grandfa;
else grandfa->setson(now,father->judge());
now->setson(father,lr^1);
father->update();
now->update();
if(grandfa!=lct) grandfa->update();
}
void splay(node *now){
if(now->isroot())return;
for(; !now->isroot(); rotate(now))
if(!now->pre->isroot())
now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now){
node *last=lct;
for(; now!=lct; last=now,now=now->pre) {
splay(now);
now->setson(last,1);
}
return last;
}
void changeroot(node *now){
access(now)->rev^=1;
splay(now);
}
void connect(node *x, node *y){
changeroot(x);
x->pre=y;
access(x);
}
void cut(node *x, node *y){
changeroot(x);
access(y);
splay(x);
x->pushdown();
x->son[1]=y->pre=lct;
x->update();
}
int query(node *x, node *y){
changeroot(x);
node *now=access(y);
return now->sum;
}
int qs[GRAPHN];
void quickSort(int l, int r) {
if(l >= r) return;
int i = l, j = r, pivot = qs[l];
while(i < j){
while(qs[j] >= pivot && i < j) j--;
while(qs[i] <= pivot && i < j) i++;
if(i < j) swap(qs[i], qs[j]);
}
qs[l] = qs[i]; qs[i] = pivot;
quickSort(l, i - 1);
quickSort(i + 1, r);
}
int STn, nums[10], st1[10][17], st2[10][17];
void ST_work1() {
for (int i = 1; i <= STn; i++) st1[i][0] = nums[i];
int t = log(STn) / log(2) + 1;
for (int j = 1; j < t; j++) {
for (int i = 1; i <= STn - (1 << j) + 1; i++)
st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
}
}
int ST_query1(int l, int r) {
int k = log(r - l + 1) / log(2);
return max(st1[l][k], st1[r - (1 << k) + 1][k]);
}
void ST_work2() {
for (int i = 1; i <= STn; i++) st1[i][0] = nums[i];
int t = log(STn) / log(2) + 1;
for (int j = 1; j < t; j++) {
for (int i = 1; i <= STn - (1 << j) + 1; i++)
st1[i][j] = min(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]);
}
}
int ST_query2(int l, int r) {
int k = log(r - l + 1) / log(2);
return min(st1[l][k], st1[r - (1 << k) + 1][k]);
}
void write(int number){
if(number < 0){
putchar('-');
number = -number;
}
if(number > 9) write(number / 10);
putchar(number % 10 + '0');
return;
}
int add_bit_oper(int a, int b){
while(b){
int sum = a ^ b;
int carry = ((unsigned)(a & b) << 1);
a = sum;
b = carry;
}
return a;
}
int main(){
int a, b, c = 0;
a = qmi(dfs(read()), 1, 100000010),
b = qmi(dfs(read()), 1, 100000010);
memset(w, 0x3f, sizeof(w));
w[1][2] = a; w[2][3] = b;
dijkstra();
c += d[3];
spfa();
c += d[3];
node *A = getnew(a);
node *B = getnew(b);
connect(A, B);
cut(A, B);
connect(A, B);
c -= query(A,B);
qs[1] = a, qs[2] = b;
quickSort(1, GRAPHN-1);
int ans = 0;
for(int i = 1; i <= GRAPHN-1; i++) ans += qs[i];
c += ans;
STn = 2;
nums[1] = a, nums[2] = b;
ST_work1(); int STans1 = ST_query1(1, 2);
ST_work2(); int STans2 = ST_query2(1, 2);
c -= STans1;
c -= STans2;
int dfloyd[GRAPHN+2][GRAPHN+2];
memset(dfloyd, 0x3f, sizeof(dfloyd));
dfloyd[1][2] = a; dfloyd[2][3] = b;
for(int k = 1; k <= GRAPHN; k++)
for(int i = 1; i <= GRAPHN; i++)
for(int j = 1; j <= GRAPHN; j++)
dfloyd[i][j] = min(dfloyd[i][j], dfloyd[i][k] + dfloyd[k][j]);
c += dfloyd[1][3];
c -= add_bit_oper(a, b);
write(qmi(dfs(c), 1, 200000010));
printf("\n");
return 0;
}by Alvis_F @ 2024-05-21 21:46:10
@Jacky0909 你这Compile Error了
而且我觉得嘛……这些只是整活用的……洛谷容纳整活题解（当然前提是你AC了）
by Jacky0909 @ 2024-05-22 17:11:06
@bca_ 这玩意本地可以运行
by 1930_ @ 2024-07-26 20:52:49
@Jacky0909 神啊