T1 数独(WOJ4218)\(\color{green}{100}\)
小模拟/cy,45min左右就调完了。
code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
char c[105][10][10];
string s;
int xs[10]={0,1,1,1,4,4,4,7,7,7};
int ys[10]={0,1,4,7,1,4,7,1,4,7};
void insert(int n,int x,int y,int k){
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
c[n][i][j]=c[n-1][i][j];
if(c[n][x][y]!='0'){
cout<<"Error!\n";
return ;
}
for(int i=1;i<=9;i++)
if(c[n][x][i]==k+'0'){
cout<<"Error:row!\n";
return ;
}
for(int i=1;i<=9;i++)
if(c[n][i][y]==k+'0'){
cout<<"Error:column!\n";
return ;
}
int wh=(x-1)/3*3+(y-1)/3+1;
for(int i=0;i<=2;i++)
for(int j=0;j<=2;j++)
if(c[n][i+xs[wh]][j+ys[wh]]==k+'0'){
cout<<"Error:square!\n";
return ;
}
cout<<"OK!\n";
c[n][x][y]=k+'0';
}
void del(int n,int x,int y){
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
c[n][i][j]=c[n-1][i][j];
if(c[n][x][y]=='0')cout<<"Error!\n";
else{cout<<"OK!\n";c[n][x][y]='0';}
}
int v[10],vn;
void query(int n,int x,int y){
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
c[n][i][j]=c[n-1][i][j];
if(c[n][x][y]!='0'){cout<<"Error!\n";return ;}
memset(v,0,sizeof(v));vn=0;
for(int i=1;i<=9;i++)
v[c[n][x][i]-'0']=1;
for(int i=1;i<=9;i++)
v[c[n][i][y]-'0']=1;
int wh=(x-1)/3*3+(y-1)/3+1;
for(int i=0;i<=2;i++)
for(int j=0;j<=2;j++)
v[c[n][i+xs[wh]][j+ys[wh]]-'0']=1;
for(int i=1;i<=9;i++)
if(!v[i])vn++;
cout<<vn<<'\n';
for(int i=1;i<=9;i++)
if(!v[i])cout<<i<<"\n";
}
int ansx,ansy;
void merge(int n,int x,int y){
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
int flag=0;
if(c[x][i][j]!='0'){
flag=1;
for(int k=1;k<=9;k++)
if(c[n][i][k]==c[x][i][j]){
flag=0;break;
}
for(int k=1;k<=9;k++)
if(c[n][k][j]==c[x][i][j]){
flag=0;break;
}
int wh=(i-1)/3*3+(j-1)/3+1;
for(int l=0;l<=2;l++)
for(int r=0;r<=2;r++)
if(c[n][l+xs[wh]][r+ys[wh]]==c[x][i][j]){
flag=0;break;
}
}
if(flag){c[n][i][j]=c[x][i][j],ansx++;continue;}
if(c[y][i][j]!='0'){
flag=1;
for(int k=1;k<=9;k++)
if(c[n][i][k]==c[y][i][j]){
flag=0;break;
}
for(int k=1;k<=9;k++)
if(c[n][k][j]==c[y][i][j]){
flag=0;break;
}
int wh=(i-1)/3*3+(j-1)/3+1;
for(int l=0;l<=2;l++)
for(int r=0;r<=2;r++)
if(c[n][l+xs[wh]][r+ys[wh]]==c[y][i][j]){
flag=0;break;
}
}
if(flag){c[n][i][j]=c[y][i][j],ansy++;continue;}
c[n][i][j]='0';
}
}
cout<<ansx<<" "<<ansy<<'\n';
ansx=0,ansy=0;
}
void print(int n){
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
c[n][i][j]=c[n-1][i][j];
for(int i=1;i<=9;i++){
cout<<"+-+-+-+-+-+-+-+-+-+\n";
for(int j=1;j<=9;j++)
cout<<"|"<<c[n][i][j];
cout<<"|\n";
}
cout<<"+-+-+-+-+-+-+-+-+-+\n";
}
int T,x,y,k;
signed main(){
freopen("sudoku.in","r",stdin);
freopen("sudoku.out","w",stdout);
for(int i=1;i<=19;i++){
cin>>s;
if(i&1)continue;
for(int j=1;j<=9;j++)
c[0][i/2][j]=s[j*2-1];
}
T=in;
for(int i=1;i<=T;i++){
cin>>s;
if(s[0]=='I')x=in,y=in,k=in,insert(i,x,y,k);
else if(s[0]=='D')x=in,y=in,del(i,x,y);
else if(s[0]=='Q')x=in,y=in,query(i,x,y);
else if(s[0]=='M')x=in,y=in,merge(i,x,y);
else print(i);
}
return 0;
}
T2 骨粉(WOJ4817)\(\color{orange}{80}\)
调了2h+.
暴力:首先有个显然的结论,每次必然选择当前最大的 \(t\) 进行操作,据此可以写出暴力。
注意到最大值最小,所以考虑二分答案。对 \(s[i]\) 二分答案,假设当前二分的答案为 \(mid\),那么要判断答案合法性。对于每个经过了 \(s[i]\) 秒后还大于 \(mid\) 的 \(t\),统计需要多少次操作才能使它小于等于 \(mid\),根据这个值和 \(s[i]\) 的大小关系来判断答案。计算的时候要向上取整,可以写成 \(\lfloor\dfrac{\cdots+x-1}{x}\rfloor\),也就是
\[\sum_{j=1}^{n}[t[j]-mid-s[i]>0]\lfloor \dfrac{t[j]-mid-s[j]+x-1}{x} \rfloor \]我们可以把 \(t\) 排序,每次就可以二分出一个 \(head\),第一个满足 \(t[head]-mid-s[i]>0\),于是就是
\[\sum_{j=head}^{n}\lfloor \dfrac{t[j]-mid-s[j]+x-1}{x} \rfloor \]这样可以 \(O(nm\log \max_t)\),做到60分。
正解是对二分的优化,我们发现这个式子和 \(j\) 有关的只有前面的 \(t[j]\),所以想要把式子拆开。又发现有 \(\lfloor \dfrac{a+b}{x} \rfloor=\lfloor \dfrac{a}{x} \rfloor+\lfloor \dfrac{b}{x} \rfloor+[a\%x+b\%x\geq x]\),因为拆开多出来的只可能会是由两者取模部分贡献的1。所以有
\[\sum_{j=head}^{n}\left( \lfloor \dfrac{t[j]}{x} \rfloor+\lfloor \dfrac{-mid-s[j]+x-1}{x} \rfloor+\left(t[j]\%x+(-mid-s[j]+x-1)\%x\geq x\right) \right) \]发现 \(\sum\limits_{j=head}^{n}\lfloor \dfrac{t[j]}{x} \rfloor\) 可以后缀和做,\(\sum\limits_{j=head}^{n}\lfloor \dfrac{-mid-s[j]+x-1}{x} \rfloor\)可以 \(O(1)\) 算,所以来看 \(\sum\limits_{j=head}^{n}\left(t[j]\%x+(-mid-s[j]+x-1)\%x\geq x\right)\),发现左边的后面一坨是个常数,移到后面,记 \(X=x-(-mid-s[j]+x-1)\%x\),所以就是求\(\sum\limits_{j=head}^{n}\left(t[j]\%x\geq X\right)\),也就是求在 \(head\sim n\) 中有多少个 \(j\) 满足 \(t[j]\%x\geq X\),是区间内值域查询,另外由于值域很大,是 \(1e18\),感觉处理起来可能会比较麻烦,所以我将这个询问转化为了在所有 \(t[j]\%x\geq X\) 中有多少个 \(j\) 属于 \(head\sim n\),于是将 \(t[j]\%x\) 和 \(j\) 离线下来按 \(t[j]\%x\) 排序,主席树维护一个 \(t[j]\%x\) 的后缀中 \(j\) 的个数,然后区间查询 \(head\sim n\) 间的 \(j\) 的数量,这样值域就在控制在 \(n\) 内了。
时间复杂度 \(O((m\log \max_t+n)\log n)\)。
细节:\((-mid-s[j]+x-1)\%x\) 由于c++
特性有时是负的,为保证我们拆分的正确性需要将其转化为正的。
因为无端地觉得应该用整体二分,实则没有起到优化的作用并且常数++,最终在不开 \(O2\) 的情况下,在L的电脑上是 \(\color{orange}{80}\),在OJ上是\(\color{orange}{90}\),开了 \(O2\) 就可以 \(\color{green}{100}\)。正解直接依次二分。
code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
bool ss;
const int N=1e5+5;
int n,m,x,maxt,t[N];
#define s(x) p[x].s
#define t(x) t[x]
#define o(x) p[x].o
struct ques{
int s,o;
friend bool operator<(const ques &a,const ques &b){
return a.s<b.s;
}
}p[N];
int ans[N];
inline int bin(int key){
int l=1,r=n,mid;
while(l<r){
mid=(l+r)>>1;
if(t[mid]<=key)l=mid+1;
else r=mid;
}
return l;
}
int tot,sum[N<<5],lc[N<<5],rc[N<<5],rt[N];
inline int newnode(){
sum[++tot]=0;
lc[tot]=rc[tot]=0;
return tot;
}
inline int built(int l,int r){
if(l==r){int p=newnode();return p;}
int mid=(l+r)>>1,p=newnode();
lc[p]=built(l,mid);
rc[p]=built(mid+1,r);
return p;
}
inline int newbuilt(int l,int r,int pre,int x){
int now=newnode();
sum[now]=sum[pre];
lc[now]=lc[pre];
rc[now]=rc[pre];
if(l==r){sum[now]++;return now;}
int mid=(l+r)>>1;
if(x<=mid)lc[now]=newbuilt(l,mid,lc[now],x);
else rc[now]=newbuilt(mid+1,r,rc[now],x);
sum[now]++;
return now;
}
inline int query(int l,int r,int p,int ql,int qr){
if(l>=ql&&r<=qr){return sum[p];}
int mid=(l+r)>>1,res=0;
if(ql<=mid)res+=query(l,mid,lc[p],ql,qr);
if(qr>mid)res+=query(mid+1,r,rc[p],ql,qr);
return res;
}
struct llmmkk{int tmodx,j;}q[N];
inline bool cmp(const llmmkk &a,const llmmkk &b){
return a.tmodx>b.tmodx;
}
int tdivx[N];
int tmodx[N];
int sumdiv[N];
inline int binq(int key){
int l=0,r=n,mid;
while(l<r){
mid=(l+r+1)>>1;
if(q[mid].tmodx<key)r=mid-1;
else l=mid;
}
return l;
}
inline bool check(int i,int mid){
int head=bin(mid+s(i)),res;
if(head==n&&t(head)<=mid+s(i))res=0;
else{
int temp=-mid-s(i)+x-1;
int tempdix=temp/x;
int tempmox=temp%x;
while(tempmox<0)tempdix--,tempmox+=x;
int h=binq(x-tempmox);
res=sumdiv[n]-sumdiv[head-1]+tempdix*(n-head+1)+query(1,n,rt[h],head,n);
}
if(res<=s(i))return 1;
else return 0;;
}
bool tt;
signed main(){
// freopen("bone.in","r",stdin);
// freopen("bone.out","w",stdout);
n=in,m=in,x=in;
for(int i=1;i<=n;i++)
t(i)=in,maxt=max(maxt,t(i));
for(int i=1;i<=m;i++)
s(i)=in,o(i)=i;
sort(t+1,t+1+n);
sort(p+1,p+1+m);
for(int i=1;i<=n;i++)
tdivx[i]=t(i)/x,tmodx[i]=t(i)%x,
q[i].tmodx=tmodx[i],q[i].j=i,
sumdiv[i]=sumdiv[i-1]+tdivx[i];
sort(q+1,q+1+n,cmp);
rt[0]=built(1,n);
for(int i=1;i<=n;i++)
rt[i]=newbuilt(1,n,rt[i-1],q[i].j);
int lastans=maxt;
for(int i=1;i<=m;i++){
int l=0,r=lastans,mid;
while(l<r){
mid=(l+r)>>1;
if(check(i,mid))r=mid;
else l=mid+1;
}
lastans=ans[o(i)]=l;
}
for(int i=1;i<=m;i++)
cout<<ans[i]<<'\n';
return 0;
}
T3 树(WOJ4206)\(\color{red}{40}\)
一眼觉得是点分治,但是感觉没时间写,于是打了40分暴力。
T4 异或(WOJ4220)\(\color{red}{20}\)
同时也是之前考过的湖南集训的大新闻,但是因为之前调了一天而没写题解从而忘记了。
同时因为时间不够了,所以 \(p=1,n\leq100\) 的暴力和 \(n=2^k\) 的结论没写,痛失30分。