当前位置:网站首页>2.13 simulation summary
2.13 simulation summary
2022-07-06 02:39:00 【wind__ whisper】
List of articles
Preface
day9
170pts
expect :100+100+20=220
actual :70+100+0=170
rnk7
There are a lot of points qwq
If you get a full score, you can take paile …
T1 Add a superfluous thing , As a result, it was given for nothing 30
T3 Violent search T It fell off , We need to take a warning , In fact, just add a small optimization .
title
Minimum partition (divide)
It should be a scientific problem .
WQS Two point template question , Because this algorithm is not too cold ,A There are also many people .
Select the number according to >= Two points …
and , Don't be afraid that the number is not equal to m m m When forced transfer ! It was right to do nothing .
combination WQS The essence of is also reasonable , Just a few points fall on this straight line , It doesn't affect me to calculate the function value with intercept , If I force the last step to take m m m A transfer , Will destroy the optimality , Get the wrong intercept .
Understanding is paramount .
Hexadecimal path (base)
Explosive liver code agricultural problem .
But it's really not too hard to think about , Use the chairman tree and line segment tree to simulate the high-precision addition and comparison .
But addition requires an interval flattening operation , The chairman tree with the lazy mark is really disgusting …
The complexity of time and space should be O ( ( n + m ) log n log V ) O((n+m)\log n\log V) O((n+m)lognlogV), From the number of addition operations, the space seems to be only O ( m log V ) O(m\log V) O(mlogV), But because other query operations need pushdown
, Drive more , So in fact, the spatial complexity is also two log Of .
The realization of the problem solution is to directly link the flattened interval to the corresponding node of an empty line segment tree , The space complexity can be optimized to single log.
Euler (eular)
It's really not that I stumble
KH This question really steps on the mark , Please take my knee !
Mo did it quite clearly before , It's a pity that this problem didn't work out .
The main thing is that my brain is a little cramped , For multiple numbers lcm
, Forgetting it can also be The maximum power of each prime factor .
Because Euler function is a product function , Consider enumerating each prime number separately p p p The contribution of .
We have : φ ( p k ) = p k − 1 ( p − 1 ) \varphi(p^k)=p^{k-1}(p-1) φ(pk)=pk−1(p−1)
therefore p p p The total contribution of this prime number must be ( p − 1 ) a p b (p-1)^ap^b (p−1)apb The appearance of .
First , p p p Must appear at least once , This sequence has n k − ⌊ n p ⌋ k n^k-\lfloor\frac{n}{p}\rfloor^k nk−⌊pn⌋k individual .
therefore p − 1 p-1 p−1 Power of contribution a a a Namely n k − ⌊ n p ⌋ k n^k-\lfloor\frac{n}{p}\rfloor^k nk−⌊pn⌋k.
Then consider how to find b b b.
At the beginning, the contribution of all sequences is 0.
Set a sequence p p p The highest number of times is m x mx mx, that m x ≥ w mx\ge w mx≥w The sequence of should have n k − ⌊ n p w ⌋ k n^k-\lfloor\frac{n}{p^w}\rfloor^k nk−⌊pwn⌋k individual .
We from 2 Start enumeration w w w, Then the contribution of the corresponding sequence is regarded as 1.
So one m x = x mx=x mx=x Sequence , It will contribute x − 1 x-1 x−1 Secondary contribution , Just in line with the meaning of the topic .( This is also a common statistical skill )
The greatest truths are the simplest , Graceful .
The total complexity is probably less than that of single log Of .
After reading this practice , The solution to the problem is …
But this min-max It's still handsome .
Then there is the conventional large-scale inversion .
Code
T1
#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
void write(ll x){
if(x>9) write(x/10);
putchar('0'+x%10);
}
const int N=2e5+100;
int n,m;
#define X(o) (2*s[o])
#define Y(o) (dp[o]+s[o]*s[o]-2*p*s[o])
ll s[N],dp[N],p;
int num[N],q[N],st,ed;
void solve(ll w,int op=0){
q[st=ed=1]=0;
for(int i=1;i<=n;i++){
while(st<ed&&s[i]*(X(q[st+1])-X(q[st]))>=(Y(q[st+1])-Y(q[st]))) ++st;
int j=q[st];
dp[i]=dp[j]+(s[i]-s[j]+p)*(s[i]-s[j]+p)+w;
num[i]=num[j]+1;
while(st<ed&&(Y(i)-Y(q[ed]))*(X(q[ed])-X(q[ed-1]))<=
(Y(q[ed])-Y(q[ed-1]))*(X(i)-X(q[ed]))) --ed;
q[++ed]=i;
//printf("i=%d j=%d dp=%lld (%lld %lld)\n",i,j,dp[i],X(i),Y(i));
//for(int j=st;j<=ed;j++) printf("%d:(%lld %lld) ",q[j],X(q[j]),Y(q[j]));
//puts("\n");
}
//printf("w=%lld num=%d dp=%lld\n",w,num[n],dp[n]);
return;
}
signed main(){
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
n=read();m=read();p=read();
for(int i=1;i<=n;i++) s[i]=read()+s[i-1];
//solve(308);return 0;
ll st=-1e16,ed=1e16;
while(st<ed){
ll mid=(st+ed+1)>>1;
solve(mid);
if(num[n]>=m) st=mid;
else ed=mid-1;
}
solve(st,1);
write(dp[n]-m*st);
return 0;
}
/* 5 aabba */
T2
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
void write(ll x){
if(x>9) write(x/10);
putchar('0'+x%10);
}
const int N=2e5+100;
const int mod=1e9+7;
int n,m,s,t,o;
struct node{
int to,nxt,w;
}p[N<<1];
int fi[N],cnt;
inline void addline(int x,int y,int w){
p[++cnt]=(node){
y,fi[x],w};fi[x]=cnt;
}
int pre[N],a[N],num;
void print(int x){
if(pre[x]) print(pre[x]);
a[++num]=x;
}
ll dis[N];
ull mi[N];
int u[N],v[N],ww[N];
int vis[N];
#define pr pair<ll,int>
#define mkp make_pair
priority_queue<pr,vector<pr>,greater<pr> >q;
void bf(){
mi[0]=1;
for(int i=1;i<=o;i++) mi[i]=mi[i-1]<<1;
for(int i=1;i<=m;i++){
addline(u[i],v[i],mi[ww[i]]);
addline(v[i],u[i],mi[ww[i]]);
}
memset(dis,0x3f,sizeof(dis));
dis[s]=0;q.push(mkp(0,s));
while(!q.empty()){
int now=q.top().second;q.pop();
if(vis[now]) continue;
vis[now]=1;
for(int i=fi[now];~i;i=p[i].nxt){
int to=p[i].to;
if(dis[to]>dis[now]+p[i].w){
dis[to]=dis[now]+p[i].w;
q.push(mkp(dis[to],to));
pre[to]=now;
}
}
}
if(pre[t]||s==t){
printf("%lld\n",dis[t]%mod);
print(t);
printf("%d\n",num);
for(int i=1;i<=num;i++) printf("%d ",a[i]);
puts("");
}
else puts("-1");
return;
}
ull hh[N][2];
#define mid ((l+r)>>1)
const int key=3;
struct tree{
int ls,rs,sum,laz;
ull h;
}tr[N*200];
int tot;
inline void pushup(int k,int l,int r){
tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum;
tr[k].h=tr[tr[k].rs].h*mi[mid-l+1]+tr[tr[k].ls].h;
return;
}
inline int copy(int x){
tr[++tot]=tr[x];
return tot;
}
inline void add(int &k,int l,int r,int w){
k=copy(k);
tr[k].sum=(r-l+1)*w;tr[k].laz=w;
tr[k].h=hh[r-l+1][w];
return;
}
inline void pushdown(int k,int l,int r){
if(l==r) return;
int o=tr[k].laz;tr[k].laz=-1;
if(o==-1) return;
add(tr[k].ls,l,mid,o);add(tr[k].rs,mid+1,r,o);
return;
}
void build(int &k,int l,int r,int w){
k=copy(0);
if(l==r){
tr[k].sum=tr[k].h=w;
hh[r-l+1][w]=tr[k].h;
return;
}
build(tr[k].ls,l,mid,w);
build(tr[k].rs,mid+1,r,w);
pushup(k,l,r);
hh[r-l+1][w]=tr[k].h;
return;
}
int findsuf(int k,int l,int r,int pl){
if(tr[k].sum==r-l+1) return r-pl+1;
if(l==r) return 0;
pushdown(k,l,r);
if(pl>mid) return findsuf(tr[k].rs,mid+1,r,pl);
else{
int res=findsuf(tr[k].ls,l,mid,pl);
if(res==mid-pl+1) return res+findsuf(tr[k].rs,mid+1,r,mid+1);
else return res;
}
}
void upd(int &k,int l,int r,int x,int y,int w){
//printf("upd: (%d %d) (%d %d) w=%d\n",l,r,x,y,w);
if(x>y) return;
if(x<=l&&r<=y){
add(k,l,r,w);return;
}
pushdown(k,l,r);
k=copy(k);
if(x<=mid) upd(tr[k].ls,l,mid,x,y,w);
if(y>mid) upd(tr[k].rs,mid+1,r,x,y,w);
pushup(k,l,r);
return;
}
bool cmp(int x,int y,int l,int r){
// x<y ? 1:0
if(tr[x].h==tr[y].h) return 0;
if(l==r) return tr[x].sum<tr[y].sum;
pushdown(x,l,r);pushdown(y,l,r);
if(tr[tr[x].rs].h!=tr[tr[y].rs].h) return cmp(tr[x].rs,tr[y].rs,mid+1,r);
else return cmp(tr[x].ls,tr[y].ls,l,mid);
}
struct bign{
int rt;
void plus(int w){
int len=findsuf(rt,1,o,w);
upd(rt,1,o,w,w+len-1,0);upd(rt,1,o,w+len,w+len,1);
return;
}
bool operator < (const bign &oth)const{
return cmp(rt,oth.rt,1,o);
}
}d[N];
struct Dis{
bign dis;
int id;
bool operator < (const Dis &oth)const{
if(tr[dis.rt].h==tr[oth.dis.rt].h) return id>oth.id;
else return oth.dis<dis;
}
};
priority_queue<Dis>que;
ll ans,mi2[N];
void calc(int k,int l,int r){
if(l==r){
ans=(ans+tr[k].sum*mi2[l-1])%mod;
return;
}
pushdown(k,l,r);
calc(tr[k].ls,l,mid);calc(tr[k].rs,mid+1,r);
return;
}
void solve(){
o+=20;
mi2[0]=1;
for(int i=1;i<=o;i++) mi2[i]=(mi2[i-1]<<1)%mod;
mi[0]=1;
for(int i=1;i<=o;i++) mi[i]=mi[i-1]*key;
for(int i=1;i<=m;i++){
++ww[i];
addline(u[i],v[i],ww[i]);
addline(v[i],u[i],ww[i]);
}
build(d[0].rt,1,o,1);//rt[0]=inf
for(int i=1;i<=n;i++) d[i].rt=d[0].rt;
build(d[s].rt,1,o,0);
que.push((Dis){
d[s],s});
while(!que.empty()){
int now=que.top().id;que.pop();
if(vis[now]) continue;
vis[now]=1;
for(int i=fi[now];~i;i=p[i].nxt){
int to=p[i].to,w=p[i].w;
bign res=d[now];res.plus(w);
if(res<d[to]){
d[to]=res;
que.push((Dis){
d[to],to});
pre[to]=now;
}
}
}
if(!pre[t]&&s!=t) puts("-1");
else{
calc(d[t].rt,1,o);
//debug("dis=%lld\n",ans);
printf("%lld\n",ans);
print(t);
printf("%d\n",num);
for(int i=1;i<=num;i++) printf("%d ",a[i]);
}
return;
}
signed main(){
freopen("base.in","r",stdin);
freopen("base.out","w",stdout);
//printf("%d\n",sizeof(tr)/1024/1024);
memset(fi,-1,sizeof(fi));cnt=-1;
tr[0].laz=-1;
n=read();m=read();s=read();t=read();
for(int i=1;i<=m;i++){
u[i]=read();v[i]=read();ww[i]=read();
o=max(o,ww[i]);
}
if(o<=20) bf();
else solve();
//solve();
return 0;
}
/* 5 aabba */
T3
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){
x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
void write(ll x){
if(x>9) write(x/10);
putchar('0'+x%10);
}
const int N=2e6+100;
const int mod=1e9+7;
inline ll ksm(ll x,ll k,ll mod){
ll res(1);
while(k){
if(k&1) res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
int n,k;
int prime[N],vis[N],tot;
void init(int n){
++n;
for(int i=2;i<=n;i++){
if(!vis[i]){
prime[++tot]=i;
}
for(int j=1;j<=tot&&prime[j]<=n/i;j++){
int now=prime[j];
vis[i*now]=1;
if(i%now==0) break;
}
}
return;
}
signed main(){
freopen("euler.in","r",stdin);
freopen("euler.out","w",stdout);
n=read();k=read();
init(max(k,n));
ll ans(1);
for(int o=1;o<=tot;o++){
ll p=prime[o];
ans=ans*ksm(p-1,ksm(n,k,mod-1)+(mod-1)-ksm(n-n/p,k,mod-1),mod)%mod;
ll now=p*p;
while(now<=n){
ans=ans*ksm(p,ksm(n,k,mod-1)+mod-1-ksm(n-n/now,k,mod-1),mod)%mod;
now*=p;
}
}
printf("%lld\n",ans);
return 0;
}
/* 5 aabba */
summary
Today, I feel that the overall topic is easier .
But there are a little too many points , and T3 It's a pity , In fact, I haven't thought about the practice of considering each prime number separately …
( Now on the topic “ Feeling ” It's better , Can't do the problem see solution Basically, there are “ Actually, I thought ” The process of .)
But still dare to push and think .
Dare to think creatively , Try multi line thinking when you encounter obstacles .
in addition , Today's rhythm is still good .
Come on tomorrow !awa
边栏推荐
- PMP每日一练 | 考试不迷路-7.5
- After changing the GCC version, make[1] appears in the compilation: cc: command not found
- Number conclusion LC skimming review - 1
- [untitled] a query SQL execution process in the database
- Bigder: I felt good about the 34/100 interview, but I didn't receive the admission
- LeetCode 103. Binary tree zigzag level order transverse - Binary Tree Series Question 5
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 17
- Day 50 - install vsftpd on ceontos6.8
- 2022 China eye Expo, Shandong vision prevention and control exhibition, myopia, China myopia correction Exhibition
- Introduction to robotframework (II) app startup of appui automation
猜你喜欢
Pat grade a 1033 to fill or not to fill
A doctor's 22 years in Huawei
Introduction to robotframework (I) brief introduction and use
Force buckle 146 LRU cache
UE4 - how to make a simple TPS role (I) - create a basic role
解决:AttributeError: ‘str‘ object has no attribute ‘decode‘
一个复制也能玩出花来
MySQL winter vacation self-study 2022 11 (9)
Zero foundation self-study STM32 - Review 2 - encapsulating GPIO registers with structures
主数据管理理论与实践
随机推荐
"Hands on learning in depth" Chapter 2 - preparatory knowledge_ 2.5 automatic differentiation_ Learning thinking and exercise answers
我把驱动换成了5.1.35,但是还是一样的错误,我现在是能连成功,但是我每做一次sql操作都会报这个
模板_求排列逆序对_基于归并排序
更换gcc版本后,编译出现make[1]: cc: Command not found
【无标题】数据库中一条查询SQL执行的过程
DDoS attacks - are we really at war?
After changing the GCC version, make[1] appears in the compilation: cc: command not found
零基础自学STM32-野火——GPIO复习篇——使用绝对地址操作GPIO
Déduisez la question d'aujourd'hui - 729. Mon emploi du temps I
Day 50 - install vsftpd on ceontos6.8
RobotFramework入门(一)简要介绍及使用
High number_ Vector algebra_ Unit vector_ Angle between vector and coordinate axis
PAT甲级 1033 To Fill or Not to Fill
Number conclusion LC skimming review - 1
在GBase 8c数据库中使用自带工具检查健康状态时,需要注意什么?
有沒有sqlcdc監控多張錶 再關聯後 sink到另外一張錶的案例啊?全部在 mysql中操作
HDU_ p1237_ Simple calculator_ stack
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 19
[Digital IC manual tearing code] Verilog asynchronous reset synchronous release | topic | principle | design | simulation
高数_向量代数_单位向量_向量与坐标轴的夹角