理科卷math·english·chinese·biology·chemistry·physics
rtrt
3月 14, 2025
归档于 2019-08-29 11:54
一套比一套炸,果然我只会做B卷,虽然我B也很差但没差到这种地步
$math$
题解
看似没法做但总会有突破口
$70%$
发现和小凯的诱惑很像,于是看$gcd$是否为$1$只要为$1$可以凑齐所有数
$n^2$枚举两两$gcd$
$80%$
我考试时思路
找到每一个数和$mod$的$gcd$,发现只要是任一$gcd$倍数就可以凑出来,于是枚举每一个数和$mod$的$gcd$,瓶颈在于统计答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 2222222
ll n,k,cnt=0;
ll a[A],dl[A],ok[A];
ll read(){
ll x=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c=='-')
f=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f*x;
}
ll gcd(ll x,ll y){
if(y==0) return x;
return gcd(y,x%y);
}
int main(){
n=read(),k=read();
for(ll i=1;i<=n;i++)
a[i]=read(),dl[++dl[0]]=a[i];
for(ll i=1;i<=dl[0];i++){
ll g=gcd(dl[i],k);
if(g==1){
printf("%lld\n",k);
for(ll j=0;j<=k-1;j++){
printf("%lld ",j);
}
return 0;
}
else {
for(ll i=g;i<k;i+=g){
ok[i]=1;
}
ok[0]=1;
}
}
for(ll i=0;i<=k;i++){
if(ok[i]) cnt++;
}
printf("%lld\n",cnt);
for(ll i=0;i<=k;i++){
if(ok[i]) printf("%lld ",i);
}
printf("\n");
}
View Code
$100%$
其实从$80%$我们就应该看出可以找到所有数$gcd$,然后只有为$gcd$倍数才可以凑出来
考试时我连这个都没有想到!
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 1010101
ll n,k,cnt=0;
ll a[A],dl[A];
ll read(){
ll f=1,x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f*x;
}
ll gcd(ll x,ll y){
if(y==0) return x;
return gcd(y,x%y);
}
int main(){
n=read(),k=read();
for(ll i=1;i<=n;i++){
a[i]=read();
while(a[i]<0){
a[i]+=k;
}
}
ll g=gcd(a[1],a[2]);
g=gcd(g,k);
for(ll i=3;i<=n;i++)
g=gcd(a[i],g);
for(ll i=0;i<k;i+=g){
cnt++;
dl[++dl[0]]=i;
}
printf("%lld\n",cnt);
for(ll i=1;i<=dl[0];i++){
printf("%lld ",dl[i]);
}
printf("\n");
}
View Code
$english$
题解
破题打了很久从$23$日打到$27$日
然而考试两个人当场$AC$
思路还算比较简单,然而很难打,不用说了我码力太弱
$ans1$还算比较简单,和学数数那个题很像,
我们找到以每一个值为最大值的最左$l$,最右$r$
设当前值位置为$now$
那么因为是异或,造成贡献的只有$now-l$中与$r-now$中二进制位相反的
设$0[x][j]$表示$1–x$中第$j$位为$0$数有多少个(这是前缀和)
类似设$1[x][j]$表示$1–x$中第$j$位为$1$数有多少个
那么$now$贡献就为$\sum\limits_{j=1}^{j<=最高位}
(0[now][j]-0[l-1][j])(1[r][j]-1[now-1][j])+(1[now][j]-1[l-1][j])(0[r][j]-0[now-1][j])$
然后问题又转化为了找到以每一个值为最大值的最左$l$,最右$r$
这里我还是用的我的老方法(愚蠢至极)
void pre(ll l,ll r,ll now,ll nowmax){
if(l>r) return ;
lef[now]=l,rig[now]=r;
if(l==r) {
len[now]=r-l+1;
return ;
}
maxn=-1,ida=0;
if(l<=now-1){
seg_max(1,l,now-1);
pre(l,now-1,ida,maxn);
}
maxn=-1,ida=0;
if(now+1<=r){
seg_max(1,now+1,r);
pre(now+1,r,ida,maxn);
}
}
二分套线段树
复杂度玄学说是$n*{log(n)^2}$然而实际跑起来只比单调栈慢$400ms$,学数数还比单调栈快
$ans2$稍难但是还是寻找突破口
先放官方题解
这是很好的转化,我的实现和他不一样
(启发式合并太难打了,事实上我打了但根本没发调)
我用的可持久化$tire$,
可持久化$tire$可以查区间
要找到右面区间有多少个$xor$当前$a[j]$比最大值大
放进$tire$树里看如果最大值当前位为$1$,你不可能比它大,必须选相反位,为$0$比它大个数就是$size$了(size下所有都比它大)
放一下实现
void work2(){
root[0]=newnode();
for(ll i=1;i<=n;i++)
root[i]=newnode(),insert(root[i-1],root[i],a[i]);
for(ll i=1;i<=n;i++){
ll tmp=0;
if(rig[i]-i>i-lef[i])
for(ll j=lef[i];j<=i;j++)
tmp=(tmp+query(root[i-1],root[rig[i]],a[j],a[i]))%mod;
if(rig[i]-i<=i-lef[i])
for(ll j=i;j<=rig[i];j++)
tmp=(tmp+query(root[lef[i]-1],root[i],a[j],a[i]))%mod;
ans2=(ans2+tmp*a[i])%mod;
}
}
ll query(ll F,ll C,ll now,ll big){
ll ans=0;
for(ll i=20;i>=0;i--){
ll num[2];
num[0]=sz[ch[C][0]]-sz[ch[F][0]];
num[1]=sz[ch[C][1]]-sz[ch[F][1]];
ll
nowbit=(now>>(i))&1,
bigbit=(big>>(i))&1;
if(bigbit) F=ch[F][nowbit^1],C=ch[C][nowbit^1];
else F=ch[F][nowbit],C=ch[C][nowbit],ans=(ans+num[nowbit^1]%mod);
}
return ans;
}
总代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 222222
const ll mod=1e9+7;
ll n,q,mx,mn=0x7fffffffff,ida,maxn,idb,thebigest,thebigestid,ans1,ans2;
ll a[A],sum[A],b[A],ls[A],rs[A],len[A],_0[A][33],_1[A][33],lef[A],rig[A],sta[A];
ll root[A];
ll sz[11111111];
ll ch[11111111][2];
ll totnode=1,top=0;
char c[10];
struct tree{
ll l,r,val,id;
}tr[A];
void init(){
for(ll i=1;i<=n;++i){
while(top&&a[sta[top]]<a[i]) rig[sta[top--]]=i-1;
sta[++top]=i;
}
while(top) rig[sta[top--]]=n;
for(ll i=n;i>=1;--i){
while(top&&a[sta[top]]<=a[i]) lef[sta[top--]]=i+1;
sta[++top]=i;
}
while(top) lef[sta[top--]]=1;
}
void pushup(ll p){
if(tr[p<<1].val>tr[p<<1|1].val){
tr[p].val=tr[p<<1].val;
tr[p].id=tr[p<<1].id;
}
else {
tr[p].val=tr[p<<1|1].val;
tr[p].id=tr[p<<1|1].id;
}
}
void built(ll p,ll l,ll r){
tr[p].l=l,tr[p].r=r;
if(l==r){
tr[p].val=a[l];
tr[p].id=l;
return ;
}
ll mid=(l+r)>>1;
built(p<<1,l,mid);
built(p<<1|1,mid+1,r);
pushup(p);
}
void seg_max(ll p,ll l,ll r){
if(tr[p].l>=l&&tr[p].r<=r){
if(tr[p].val>maxn){
maxn=tr[p].val;
ida=tr[p].id;
}
return ;
}
ll mid=(tr[p].l+tr[p].r)>>1;
if(mid>=l)
seg_max(p<<1,l,r);
if(mid<r)
seg_max(p<<1|1,l,r);
}
void pre(ll l,ll r,ll now,ll nowmax){
if(l>r) return ;
lef[now]=l,rig[now]=r;
if(l==r) {
len[now]=r-l+1;
return ;
}
maxn=-1,ida=0;
if(l<=now-1){
seg_max(1,l,now-1);
pre(l,now-1,ida,maxn);
}
maxn=-1,ida=0;
if(now+1<=r){
seg_max(1,now+1,r);
pre(now+1,r,ida,maxn);
}
}
void work1(){
for(ll j=0;j<=20;j++)
for(ll i=1;i<=n;i++){
_0[i][j]=_0[i-1][j];
_1[i][j]=_1[i-1][j];
if((a[i]&(1<<j))) _1[i][j]++;
else _0[i][j]++;
}
for(ll i=1;i<=n;i++){
ll tmp=0;
for(ll j=0;j<=20;j++){
ll
l0=_0[i][j]-_0[lef[i]-1][j],
r0=_0[rig[i]][j]-_0[i-1][j],
l1=_1[i][j]-_1[lef[i]-1][j],
r1=_1[rig[i]][j]-_1[i-1][j];
tmp=(tmp+(l0*(r1%mod*(1<<j)%mod)))%mod;
tmp=(tmp+(l1*(r0%mod*(1<<j)%mod)))%mod;
}ans1=(ans1+tmp*a[i])%mod;
}
}
ll newnode(){
memset(ch[totnode],0,sizeof(ch[totnode]));
sz[totnode]=0;
return totnode++;
}
//F之前树 C现在树
inline void insert(ll F,ll C,ll val){
for(ll i=20;i>=0;i--){
ll bit=(val>>i)&1;
if(!ch[C][bit]){
ch[C][bit]=newnode();
ch[C][!bit]=ch[F][!bit];
sz[ch[C][bit]]=sz[ch[F][bit]];
}
C=ch[C][bit],F=ch[F][bit];
sz[C]++;
}
}
ll query(ll F,ll C,ll now,ll big){
ll ans=0;
for(ll i=20;i>=0;i--){
ll num[2];
num[0]=sz[ch[C][0]]-sz[ch[F][0]];
num[1]=sz[ch[C][1]]-sz[ch[F][1]];
ll
nowbit=(now>>(i))&1,
bigbit=(big>>(i))&1;
if(bigbit) F=ch[F][nowbit^1],C=ch[C][nowbit^1];
else F=ch[F][nowbit],C=ch[C][nowbit],ans=(ans+num[nowbit^1]%mod);
}
return ans;
}
void work2(){
root[0]=newnode();
for(ll i=1;i<=n;i++)
root[i]=newnode(),insert(root[i-1],root[i],a[i]);
for(ll i=1;i<=n;i++){
ll tmp=0;
if(rig[i]-i>i-lef[i])
for(ll j=lef[i];j<=i;j++)
tmp=(tmp+query(root[i-1],root[rig[i]],a[j],a[i]))%mod;
if(rig[i]-i<=i-lef[i])
for(ll j=i;j<=rig[i];j++)
tmp=(tmp+query(root[lef[i]-1],root[i],a[j],a[i]))%mod;
ans2=(ans2+tmp*a[i])%mod;
}
}
int main(){
scanf("%lld%lld",&n,&q);
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(a[i]>mx)
ida=i,mx=a[i];
mn=min(mn,a[i]);
}
thebigestid=ida;
built(1,1,n);
pre(1,n,ida,a[ida]);
work1();work2();
if(q==1)printf("%lld\n",ans1);
if(q==2)printf("%lld\n",ans2);
if(q==3)printf("%lld\n%lld\n",ans1,ans2);
}
View Code
$chinese$
题解
炼字简称练字(其实是我懒得改了)
真·吃了语文的亏
考试一直在做这个题($2$小时左右)然而还是只会暴力(然后更加蠢的是我打了暴力没有打表,别人打表$60$分,我暴力$45$)
首先题目中式子含义要搞清楚
其实他就是让你统计所有方案有多少个练字
你放一个练字那么贡献就是当前所有方案数$*1$
当前方案数如何求呢?
假设当前在$x$,$y$填练字,,练字为$i$
那么$x$所在行剩下$m-1$个位置只能小$(i-1)^{(m-1)}$
类似的$y$所在列剩下$(i-1)^{(n-1)}$
剩下位置随便填
这样为什么是对的,(即为什么是练字个数)
假设你随便填里有一个练字,你算当前练字个数算了一个,下一次考虑时又考虑当前这个
或者你这么想,在这$(i-1)^{(n-1)}*(i-1)^{(m-1)}k^{(n-1)(m-1)}$每一种方案都计算了当前这个练字,,每种方案贡献为$1$
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,ans=0;
const ll mod=1e9+7;
ll meng(ll x,ll k){
ll ans=1;
for(;k;k>>=1,x=x*x%mod){
if(k&1)
ans=ans*x%mod;
}
return ans;
}
ll k;
int main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(ll i=1;i<=k;i++)
ans=(ans+meng(i-1,n-1)%mod*meng(i-1,m-1)%mod*meng(k,(n-1)*(m-1))%mod)%mod;
ans=(ans*n%mod*m%mod)%mod;
printf("%lld\n",ans);
}
View Code
$biology$
题解
$dp$,思路没有见过,还是要多见见,
首先暴力转移枚举每一个方格最小的复杂度$n^2*m^2$
思考优化
绝对值很恶心,考虑去掉绝对值
拆成$-x-y$,$+x+y$,$-x+y$,$+x-y$
然后发现一个性质我们把一个原本应该是$-x-y$的拆成$4$个另外三个并不会比$-x-y$变优
于是我们愉快维护四个最大值变量就行了
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2101
ll n,m,cnt=0,st=0,ans=0,mx1=0,mx2=0,mx3=0,mx4=0;
ll tmp1,tmp2,tmp3,tmp4,sta;
ll read(){
ll x=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c=='-')
f=-1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f*x;
}
struct node{
ll x,y,val;
friend bool operator < (const node &a,const node &b){
return a.val<b.val;
}
}c[maxn*maxn];
ll b[maxn][maxn],f[maxn*maxn];
int main(){
n=read(),m=read();
for(ll i=1;i<=n;i++)
for(ll j=1,a;j<=m;j++){
scanf("%lld",&a);
if(a==0) continue;
++cnt;
c[cnt].x=i;
c[cnt].y=j;
c[cnt].val=a;
}
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++){
scanf("%lld",&b[i][j]);
}
sort(c+1,c+cnt+1);
for(ll i=cnt;i>=2;i--){
if(c[i].val!=c[i-1].val){
sta=i;
}
}
for(ll i=1;i<sta;i++){
ll x=c[i].x,y=c[i].y;
f[i]=b[c[i].x][c[i].y];
// printf("f[%lld]=%lld x=%lld y=%lld\n",i,f[i],x,y);
tmp1=max(tmp1,f[i]-x-y);
tmp2=max(tmp2,f[i]-x+y);
tmp3=max(tmp3,f[i]+x-y);
tmp4=max(tmp4,f[i]+x+y);
ans=max(ans,f[i]);
}
for(ll i=sta;i<=cnt;i++){
ll x=c[i].x,y=c[i].y;
if(c[i].val!=c[i-1].val){
mx1=max(mx1,tmp1);
mx2=max(mx2,tmp2);
mx3=max(mx3,tmp3);
mx4=max(mx4,tmp4);
}
// printf("mx1=%lld 2=%lld 3=%lld 4=%lld\n",mx1,mx2,mx3,mx4);
ll an=0;
an=max(an,mx1+x+y);
an=max(an,mx2+x-y);
an=max(an,mx3-x+y);
an=max(an,mx4-x-y);
f[i]=an+b[c[i].x][c[i].y];
tmp1=max(tmp1,f[i]-x-y);//左上
tmp2=max(tmp2,f[i]-x+y);//右上
tmp3=max(tmp3,f[i]+x-y);//左下
tmp4=max(tmp4,f[i]+x+y);//右下
ans=max(ans,f[i]);
}
// for(ll i=1;i<=cnt;i++){
// printf("%lld\n",f[i]);
// }
printf("%lld\n",ans);
}
View Code
$physics$
题解
前缀和?
为什么选择前缀和,前缀和查询$O(1)$我们主要时间在查询上$n^3$(或)$n^2*log(n)$,修改$n^2$绝对可以接受
于是前缀和就完了
满足二分性质可以进行二分,然而我没有打
类似于二分答案枚举当前可以分成的$n^2*log(n)$
void ask(){
int l=1,r=ans;
while(l<=r){
int mid=(l+r)>>1;
if(judge(mid)) l=mid+1;
else r=mid-1;
}
}
我暴力$+$剪枝$AC$思考怎么剪枝
首先枚举是越修改越小的,我们可以记录下当前答案,然后下次验证时在当前答案基础上验证就行了
然后还有记录当前所有符合答案
cnt++;
mo[cnt].x=x,mo[cnt].y=y,mo[cnt].ok=1,mo[cnt].len=i;
验证时
for(ll j=1;j<=cnt;j++)
if(mo[j].ok){
if(x>=mo[cnt].x&&x<=mo[cnt].x+mo[cnt].len-1&&y>=mo[cnt].y&&y<=mo[cnt].y+mo[cnt].len-1) mo[j].ok=0;
else allok=1;
}
if(allok) printf("%d\n",nowans);
else pre(),printf("%d\n",nowans);
复杂度与变化次数相关
代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define A 1111
char a[A][A];
ll cnt=0,n,m,k,maxx,nowans,nowlefx,nowlefy,nowrigx,nowrigy,llll,upup;
ll sum[A][A];
struct node{
ll x,y,len,ok;
}mo[1111111];
void pre(){
cnt=0;
for(ll i=nowans;i>=1;i--){
for(ll x=1;x<=n-i+1;x++){
for(ll y=1;y<=n-i+1;y++)
if(sum[x+i-1][y+i-1]+sum[x-1][y-1]-sum[x-1][y+i-1]-sum[x+i-1][y-1]==0){
cnt++;
mo[cnt].x=x,mo[cnt].y=y,mo[cnt].ok=1,mo[cnt].len=i;
nowans=i;
}
}
if(cnt) return ;
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(ll i=1;i<=n;i++){
scanf("%s",a[i]+1);
for(ll j=1;j<=m;j++)
if(a[i][j]=='-')
sum[i][j]=1;
}
ll x,y;
scanf("%d%d",&x,&y);
sum[x][y]=1;
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
nowans=n;
pre();
printf("%d\n",nowans);
for(ll i=2,x,y;i<=k;i++){
scanf("%d%d",&x,&y);
for(ll i=x;i<=n;i++)
for(ll j=y;j<=m;j++)
sum[i][j]++;
ll allok=0;
for(ll j=1;j<=cnt;j++)
if(mo[j].ok){
if(x>=mo[cnt].x&&x<=mo[cnt].x+mo[cnt].len-1&&y>=mo[cnt].y&&y<=mo[cnt].y+mo[cnt].len-1) mo[j].ok=0;
else allok=1;
}
if(allok) printf("%d\n",nowans);
else pre(),printf("%d\n",nowans);
}
}
View Code