NOIp2018集训test-9-19(am&pm)
2024-09-06 06:08:22
AM
这是一套在长沙考过而且我能记得全部正解的题，然后期望得分300实际得分155。
T1
很套路,随便搞（我当年是怎么花大半场时间写T1并且写出现在两倍长的代码的？？）
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=2e5+;
using namespace std;
typedef long long LL;
typedef double db;
int n,m,cnt[];
LL a[N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} map<LL,int>mp; LL mo(LL x,LL p) { return x>=p?x-p:x;}
LL ksc(LL a,LL b,LL p) {
if(a>=p) a%=p;
if(b>=p) b%=p;
if(a<b) swap(a,b);
LL bs=a,rs=;
while(b) {
if(b&) rs=mo(rs+bs,p);
bs=mo(bs+bs,p);
b>>=;
}
return rs;
} #define ANS
int main() {
#ifdef ANS
freopen("meaningless.in","r",stdin);
freopen("meaningless.out","w",stdout);
#endif
read(n); read(m);
For(i,,n) {
read(a[i]);
For(j,,) if(a[i]&(1LL<<j))
cnt[j]++;
mp[a[i]]++;
}
For(i,,m) {
int o;
LL x,y,p;
read(o);
if(o==) {
read(x); read(y);
if(x==y) continue;
if(mp[x]) {
int tp=mp[x];
For(j,,) {
if((x&(1LL<<j))&&!(y&(1LL<<j))) {
cnt[j]-=tp;
}
else if(!(x&(1LL<<j))&&(y&(1LL<<j))){
cnt[j]+=tp;
}
}
mp[y]+=tp;
mp[x]=;
}
}
else {
read(p);
LL bs=1LL,ans=;
For(i,,) {
ans=mo(ans+ksc((LL)cnt[i]*(n-cnt[i])*,bs,p),p);
bs=bs*2LL%p;
}
printf("%lld\n",ans);
}
}
//cerr<<clock()<<endl;
Formylove;
}
T2
一开始一直在想数位dp,事实证明当初我不会数位dp现在仍然不会，然后看了下lucas发现很好做啊，结果少了一句话——sum[0][0]没有赋值(手拍就是不靠谱)，直接炸了45分。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=,p=;
using namespace std;
typedef long long LL;
typedef double db;
int T,C[p+][p+],sum[p+][p+];
LL n,k,fac[N],inv[N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} LL lucas(LL n,LL m) {
if(n<p&&m<p) return C[n][m];
return lucas(n/p,m/p)*lucas(n%p,m%p)%p;
} LL calc(LL n,LL m) {
if(n<=p&&m<=p) return sum[n][m];
LL t1=m/p,t2=m%p,rs;
if(t1) rs=calc(n/p,t1-)*calc(n%p,)%p;
else rs=;
rs=(rs+lucas(n/p,t1)*calc(n%p,t2)%p)%p;
return rs;
} #define ANS
int main() {
#ifdef ANS
freopen("quondam.in","r",stdin);
freopen("quondam.out","w",stdout);
#endif
read(T);
For(i,,p) C[i][]=;
For(i,,p) For(j,,i) C[i][j]=(C[i-][j-]+C[i-][j])%p;
sum[][]=;
For(i,,p) {
sum[i][]=;
For(j,,p) sum[i][j]=(sum[i][j-]+C[i][j])%p;
}
while(T--) {
read(n); read(k);
LL ans=calc(n,k);
printf("%lld\n",ans);
}
//cerr<<clock()<<endl;
Formylove;
}
T3
对这题影响贼深刻，打t2之前打的t3,以为稳了，结果直接爆0。一是我经常犯的一手写队列就出错，调用队首元素总是把que[ql]直接写成ql，二是写的时候不知为何没开滚动数组，而是把更新签到数组存下来（好像和滚动是一个意思来着，无所谓了），因为要插两次，第二次插之前就复原一次，结果如果k是1的话第一次是没插的，一复原就跳到原来去了，相当于滚动数组某次没做dp却把o^=1。
一开始写的时候sb地把攻击力相同的点合并了，显然是不能合并的，因为种类不同，背包同种类之间是无差的。实际上有没有攻击力相同的点是无所谓的做法是相同的。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=,P=;
using namespace std;
typedef long long LL;
typedef double db;
int n,m,sa[N],tot,sumnow;
LL ans,cc[N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} struct node {
int v,cnt;
friend bool operator <(const node&A,const node&B) {
return A.v>B.v;
}
}p[]; LL mo(LL x) {
if(x<) {
int debug=;
}
return x<?x+P:(x>=P?x-P:x);
} LL f[N],prf[N];
int que[N],ql,qr;
void ins(int v,int cnt) {
if(!cnt) return;
For(w,,v-) {
ql=; qr=-;
LL tp=;
for(int i=w;i<=m;i+=v) {
while(ql<=qr&&(i-que[ql])/v>cnt) {
tp=mo(tp-prf[que[ql]]); ql++;
}
prf[i]=f[i];
f[i]=mo(f[i]+tp);
tp=mo(tp+prf[i]);
que[++qr]=i;
}
}
} #define ANS
int main() {
#ifdef ANS
freopen("refrigerator.in","r",stdin);
freopen("refrigerator.out","w",stdout);
#endif
read(n); read(m);
For(i,,n) {
read(p[i].cnt); read(p[i].v);
}
sort(p+,p+n+);
For(i,,n) sumnow+=p[i].cnt*p[i].v;
f[]=;
if(sumnow<m) ans++;
For(i,,n) {
sumnow-=p[i].cnt*p[i].v;
ins(p[i].v,p[i].cnt-);
For(s,max(,m-sumnow-p[i].v),m-sumnow-)
ans=mo(ans+f[s]);
if(p[i].cnt-) For(j,,m) f[j]=prf[j];
ins(p[i].v,p[i].cnt);
}
printf("%lld\n",ans);
//cerr<<clock()<<endl;
Formylove;
}
PM
也是一年前做过的，太菜还是做不求来。
T1segment
两种做法，标解是个套路，把每个修改拆成左右两边然后按左边排序，遇见左端点就加进set遇见右端点就erase，每次遇见点的时候上个点到这个点的区间间的最大值就是set里的最大值。
我忘了这个套路，然后很sb地把修改按a大小排序，从大到小覆盖区间，每个区间第一次被覆盖的时候就是它最后的答案。用set维护区间，一开始放进一个(1,n，未覆盖)的点，每次在set里把能覆盖的区间找出来，已经被覆盖的一段连续区间合并，复杂度就很ok。也还是很好写的，stl就是好。
然而我一开始只有80pt,因为1e18的时候r-l已经是Longlong了没取膜，再乘一个int就爆了。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=1e5+,p=;
using namespace std;
typedef long long LL;
typedef double db;
int m;
LL n,ans; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} struct QS {
LL l,r,a;
friend bool operator <(const QS&A,const QS&B) {
return A.a>B.a;
}
}q[N]; struct node {
LL l,r;
int ok;
node(){}
node(LL l,LL r,int ok):l(l),r(r),ok(ok){}
friend bool operator <(const node&A,const node&B) {
return A.r<B.r;
}
};
set<node>s;
#define IT set<node>::iterator
LL mo(LL x) { return (x%p+p)%p; }
LL pf(LL x) { return x*x%p; } #define ANS
int main() {
#ifdef ANS
freopen("segment.in","r",stdin);
freopen("segment.out","w",stdout);
#endif
read(n); read(m);
For(i,,m) {
read(q[i].l);
read(q[i].r);
read(q[i].a);
}
sort(q+,q+m+);
s.insert(node(,n,));
For(i,,m) {
node t=node(q[i].l,q[i].r,);
node x;
node nx=node(,,),nl=node(,,),nr=node(,,);
IT it=s.lower_bound(t);
for(;;) {
if(it==s.end()) break;
x=*it;
s.erase(it--);
if(x.l>t.l&&x.r<t.r) {
if(!x.ok) ans=mo(ans+pf(q[i].a%p)*((x.r-x.l+)%p)%p);
}
if(x.r>=t.r) {
if(!x.ok) ans=mo(ans+pf(q[i].a%p)*(((t.r-max(t.l,x.l)+))%p)%p);
if(!x.ok&&x.r>t.r) {
nr=node(t.r+,x.r,);
nx.r=t.r;
}
else nx.r=x.r;
}
if(x.l<=t.l) {
if(!x.ok&&!(x.r>=t.r)) ans=mo(ans+pf(q[i].a%p)*((x.r-t.l+)%p)%p);
if(!x.ok&&x.l<t.l) {
nl=node(x.l,t.l-,);
nx.l=t.l;
}
else nx.l=x.l;
break;
}
}
if(nx.l!=) s.insert(nx);
if(nl.l!=) s.insert(nl);
if(nr.l!=) s.insert(nr);
}
printf("%lld\n",ans);
//cerr<<clock()<<endl;
Formylove;
}
T2 hotel
不知道为什么没有切这道题，有时候看到题觉得很麻烦就懒得动脑子去想，就想打个暴力部分分什么的就走，也可能没把题意理解清楚，看漏题上的条件之类的也是我经常犯的错误，题面往往是蕴含很多信息的，需要去理解，但我一看到不能秒懂的题面就会觉得头疼，这类题往往即使简单也做不出来。
前30n^2模拟，中间30线段树维护非0区间的答案。其实读懂题这步就直接通向标解了。
显然是把每个位置现在还能装多少人用线段树维护，题面告诉你这个东西非负，你把线段树区间维护非0段的信息改成维护非最小值的信息，随便处理一下就好了。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=3e5+;
using namespace std;
typedef long long LL;
typedef double db;
int n,m,w[N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} LL sg[N<<],mi[N<<],lz[N<<],sl[N<<],sr[N<<];
#define lc (x<<1)
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)
LL get_all(LL l) { return (l+)*l/; } void down(int x,int l,int r) {
if(!lz[x]) return;
mi[lc]+=lz[x]; lz[lc]+=lz[x];
mi[rc]+=lz[x]; lz[rc]+=lz[x];
lz[x]=;
} void upd(int x,int l,int r) {
if(mi[lc]==mi[rc]) {
mi[x]=mi[lc];
sg[x]=sg[lc]+sg[rc]+sr[lc]*sl[rc];
sr[x]=(sr[rc]==r-mid?sr[lc]+r-mid:sr[rc]);
sl[x]=(sl[lc]==mid-l+?sl[rc]+mid-l+:sl[lc]);
}
else if(mi[lc]<mi[rc]) {
mi[x]=mi[lc]; sg[x]=sg[lc]+get_all(r-mid)+sr[lc]*(r-mid);
sl[x]=sl[lc]; sr[x]=sr[lc]+r-mid;
}
else {
mi[x]=mi[rc]; sg[x]=sg[rc]+get_all(mid-l+)+sl[rc]*(mid-l+);
sr[x]=sr[rc]; sl[x]=sl[rc]+mid-l+;
}
} void build(int x,int l,int r) {
if(l==r) {
sg[x]=sl[x]=sr[x]=;
mi[x]=w[l];
return;
}
build(lc,l,mid); build(rc,mid+,r);
upd(x,l,r);
} void update(int x,int l,int r,int ql,int qr,LL w) {
if(l>=ql&&r<=qr) {
mi[x]+=w; lz[x]+=w; return ;
}
down(x,l,r);
if(ql<=mid) update(lc,l,mid,ql,qr,w);
if(qr>mid) update(rc,mid+,r,ql,qr,w);
upd(x,l,r);
} LL nlen;
LL qry(int x,int l,int r,int ql,int qr) {
if(l>=ql&&r<=qr) {
if(mi[x]>) {
LL rs=get_all(r-l+)+nlen*(r-l+);
nlen+=(r-l+);
return rs;
}
LL rs=sg[x]+nlen*sl[x];
if(sr[x]==r-l+) nlen+=sr[x];
else nlen=sr[x];
return rs;
}
down(x,l,r);
LL rs=;
if(ql<=mid) rs+=qry(lc,l,mid,ql,qr);
if(qr>mid) rs+=qry(rc,mid+,r,ql,qr);
return rs;
} #define ANS
int main() {
#ifdef ANS
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
#endif
read(n); read(m);
For(i,,n) read(w[i]);
if(n<=-&&m<=-) {
For(i,,m) {
int o,l,r,x;
read(o); read(l); read(r);
if(o==) {
read(x);
For(j,l,r) w[j]-=x;
}
else {
LL tp=,ans=;
For(j,l,r) {
if(w[j]!=) tp++;
else tp=;
if(j==r||w[j+]==)
ans+=(tp+)*tp/;
}
printf("%lld\n",ans);
}
}
}
else {
build(,,n);
For(i,,m) {
int o,l,r,x;
read(o); read(l); read(r);
if(o==) {
read(x);
update(,,n,l,r,-x);
}
else {
nlen=;
LL ans=qry(,,n,l,r);
printf("%lld\n",ans);
}
}
}
//cerr<<clock()<<endl;
Formylove;
}
T3recursion
我的数学很不好，对数字一类的东西总是很没有感觉，数学好能推柿子或者对数字有感觉的人这题应该是秒切的。但我打了半天表就只看出g是f的前缀和，硬是没看出g[g[]]是i*f的前缀和。
现在还不会证，等ycl大佬分享吧。
打表发现是前缀和以及f[i]代表i出现的次数，就随便搞了（有点像分块优化的感觉？）。
//Achen
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
#define Formylove return 0
const int N=1e6+,p=;
using namespace std;
typedef long long LL;
typedef double db;
int n;
int f[N]; template<typename T>void read(T &x) {
T f=; x=; char ch=getchar();
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} LL mo(LL x) { return x>=p?x-p:x; } int F(int n) {
if(n==) f[n]=;
if(!f[n]) {
return +F(n-F(F(n-)));
}
return f[n];
} LL dc(LL l,LL r) { return (l+r)*(r-l+)/%p; } #define ANS
int main() {
#ifdef ANS
freopen("recursion.in","r",stdin);
freopen("recursion.out","w",stdout);
#endif
int tot=;
For(i,,) f[i]=F(i);
read(n);
int now=;
LL g=,gg=;
for(int i=;;i++) {
if(now+f[i]>n) {
g=mo(g+i*(n-now+)%p);
gg=mo(gg+i*dc(now,n)%p);
break;
}
g=mo(g+i*f[i]%p);
gg=mo(gg+i*dc(now,now+f[i]-)%p);
now+=f[i];
}
printf("%lld %lld\n",g,gg);
Formylove;
}
最新文章
- Mac下环境变量配置
- Linux之服务器时间同步
- （转）Eclipse平台技术概述
- [转]fedora启动telnet服务
- Android 自定义View修炼-Android中常见的热门标签的流式布局的实现
- 【Python开发实战】Python环境的配置
- IE 调试JS加断点不管用 增加debugger
- spring security maven dependency
- Spring+SpringMVC+MyBatis深入学习及搭建(七)——MyBatis延迟加载
- 香港服务器PING知识知多少？
- Winform 最小化双击显示，最小化右键退出。退出
- 栈（LIFO）
- response slider
- 20165225《Java程序设计》第九周学习总结
- 【RPC】综述
- Python3.x：import urllib2报错解决方案
- 中国铁路基于Intel架构超大规模OpenStack行业云的性能优化研究
- avaweb(三十二)——JDBC学习入门
- [实战]MVC5+EF6+MySql企业网盘实战(14)——思考
- Mac删除.svn文件
热门文章
- {"timestamp":"2019-11-12T02:39:28.949+0000","status":415,"error":"Unsupported Media Type","message":"Content type 'text/plain;charset=UTF-8' not supported","path":&quo
- 关于linux centos7 vmware 和windows7 文件共享笔记
- war包里面文件的修改方式
- Robot Framework：环境安装
- 二维差分前缀和——cf1202D(好题）
- 微信小程序 在使用wx.request时显示加载中
- (9)centos7 安装与解压
- Codeforces 1173B Nauuo and Chess
- Rollei SL66 使用说明
- 8.1_springboot2.x之Actuator应用监控