当前位置:网站首页>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
边栏推荐
- UE4 - how to make a simple TPS role (I) - create a basic role
- 2345 file shredding, powerful file deletion tool, unbound pure extract version
- ReferenceError: primordials is not defined错误解决
- Ue4- how to make a simple TPS role (II) - realize the basic movement of the role
- Redis installation
- 主数据管理理论与实践
- 更换gcc版本后,编译出现make[1]: cc: Command not found
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 14
- MySQL winter vacation self-study 2022 11 (5)
- Reset nodejs of the system
猜你喜欢
Crawler (9) - scrape framework (1) | scrape asynchronous web crawler framework
Introduction to robotframework (II) app startup of appui automation
QT release exe software and modify exe application icon
Master data management theory and Practice
Deeply analyze the chain 2+1 mode, and subvert the traditional thinking of selling goods?
Qt发布exe软件及修改exe应用程序图标
技术管理进阶——什么是管理者之体力、脑力、心力
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 18
Déduisez la question d'aujourd'hui - 729. Mon emploi du temps I
Pat grade a 1033 to fill or not to fill
随机推荐
剑指 Offer 29. 顺时针打印矩阵
QT release exe software and modify exe application icon
技术管理进阶——什么是管理者之体力、脑力、心力
Redis skip table
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 13
Force buckle 146 LRU cache
Large scale DDoS attacks take Myanmar offline
ftp上传文件时出现 550 Permission denied,不是用户权限问题
Introduction to robotframework (III) Baidu search of webui automation
MySQL winter vacation self-study 2022 11 (9)
DDoS attacks - are we really at war?
Zero foundation self-study STM32 - Review 2 - encapsulating GPIO registers with structures
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 15
MySQL winter vacation self-study 2022 11 (5)
Redis delete policy
大厂镜像库
Day 50 - install vsftpd on ceontos6.8
一个复制也能玩出花来
Differences and usage scenarios between TCP and UDP
Crawler (9) - scrape framework (1) | scrape asynchronous web crawler framework