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分。
![洪泛路由模拟（Java實作）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)