Date 2025.10.6
在 Print 之前
這場(chǎng)比賽打的不好，T1 沒(méi)判邊界掛了 \(50 pts\)，T2、T3 都只打了 \(60 pts\)，總的來(lái)說(shuō)不算太好。
A - 玩具
P.S. \(n \le 100000 \quad t \le 100000 \quad w_{i} \le 100 \quad k_{i} \le 100\)
說(shuō)真的這題我做了 \(90 min\)，原本以為很簡(jiǎn)單（事實(shí)上也是）但還是想了很久。
不難發(fā)現(xiàn)，只需要在每次處理前綴和的余數(shù)時(shí)記錄一下位置，便可以二分解決。
時(shí)間復(fù)雜度：\(O(n \times k \times logn)\)。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=1e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
struct node {
ll l,r,kl,wl;
} b[N];
ll n,m,a[N],s,sum[N];
bool vis[105];
vector<ll> num,f[105][105];
inline void solve() {
m=read(),n=read();
for(ll i=1;i<=n;i++) {
a[i]=read();
sum[i]=sum[i-1]+a[i];
}
for(ll i=1;i<=m;i++) {
b[i]={read(),read(),read(),read()};
if(!vis[b[i].kl]) {
num.push_back(b[i].kl);
}
vis[b[i].kl]=1;
}
for(auto it : num) {
for(ll i=0;i<=n;i++) {
f[it][sum[i]%it].push_back(i);
}
}
s=read();
for(ll i=1;i<=m;i++) {
ll l=b[i].l,r=b[i].r,kl=b[i].kl;
bool fl=0;
for(ll j=0;j<kl;j++) {
ll pl=0,pr=f[kl][j].size()-1,cntl=-1,cntr=-1;
while(pl<=pr) {
ll mid=(pl+pr>>1);
if(f[kl][j][mid]>=l-1) {
cntl=mid;
pr=mid-1;
}
else {
pl=mid+1;
}
}
pl=cntl+1,pr=f[kl][j].size()-1;
while(pl<=pr) {
ll mid=(pl+pr>>1);
if(f[kl][j][mid]<=r) {
cntr=mid;
pl=mid+1;
}
else {
pr=mid-1;
}
}
if(cntr-cntl>=1&&cntl>=0&&cntr>=0) {
fl=1;
break;
}
}
if(fl) {
s+=b[i].wl;
}
else {
s-=b[i].wl;
}
}
print(s);
}
praise_long_long main() {
// freopen("toy.in","r",stdin);
// freopen("toy.out","w",stdout);
ll T=1;
// T=read();
while(T--) {
solve();
}
return 0;
}
/**/
B - 序列
先把每種時(shí)間有幾個(gè) \(a_i\) 統(tǒng)計(jì)出來(lái)，做一遍前綴和，那么對(duì)于每個(gè) \(g\) 合法的 \(a_i\) 區(qū)間是類似于 \([g, g + k] \cup [2g, 2g + k] \dots\) 的區(qū)間，所以可以利用前綴和和差分來(lái)實(shí)現(xiàn)。
時(shí)間復(fù)雜度：\(O(A \ln A)\)，其中 \(A\) 為 \(a_i\) 的最大值。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=2e6+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,kl,f,a[N],mx,sum[N],num[N];
vector<ll> ans;
inline void solve() {
n=read(),kl=read(),f=read();
ans.clear();
mx=0;
memset(sum,0,sizeof(sum));
memset(num,0,sizeof(num));
for(ll i=1;i<=n;i++) {
a[i]=read();
mx=max(mx,a[i]);
num[a[i]]++;
sum[max(1ll,a[i]-kl)]++;
sum[a[i]+1]--;
}
for(ll i=1;i<=mx;i++) {
num[i]+=num[i-1];
sum[i]+=sum[i-1];
}
for(ll i=1;i<=mx;i++) {
if(i<=kl) {
if(num[mx]-num[i-1]>=n-f) {
ans.push_back(i);
}
}
else {
ll cnt=0,numl=i;
while(numl<=mx) {
cnt+=sum[numl];
numl+=i;
}
if(cnt>=n-f) {
ans.push_back(i);
}
}
}
for(auto it : ans) {
print(it);
putchar(' ');
}
puts("");
}
praise_long_long main() {
// freopen("seq.in","r",stdin);
// freopen("seq.out","w",stdout);
ll T=1;
T=read();
while(T--) {
solve();
}
return 0;
}
/**/
C - 文件
鄙人在洛谷上寫了篇題解，這里直接復(fù)制。
暴力
事實(shí)上暴力十分簡(jiǎn)單，在每次交換時(shí)只是交換位置的話會(huì)更快一些。
時(shí)間復(fù)雜度：\(O(q\times n \times m)\)。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=1e3+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll num[N][N],n,m,q;
pll kl[N][N];
string a[N][N];
inline void solve() {
cin>>n>>m>>q;
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=m;j++) {
cin>>a[i][j];
num[i][j]=(i-1)*m+j;
}
}
while(q--) {
ll x,y,xl,yl,len,cl;
cin>>x>>y>>xl>>yl>>len>>cl;
for(ll i=0;i<len;i++) {
for(ll j=0;j<cl;j++) {
swap(num[x+i][y+j],num[xl+i][yl+j]);
}
}
}
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=m;j++) {
ll num1=num[i][j]%m,num2=(num[i][j]-num1)/m+1;
if(num1==0) {
num2--;
num1+=m;
}
cout<<a[num2][num1]<<' ';
}
cout<<'\n';
}
}
praise_long_long main() {
// freopen("file.in","r",stdin);
// freopen("file.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
ll T=1;
// T=read();
while(T--) {
solve();
}
return 0;
}
/**/
正解
我們可以想象一下，每次只交換兩個(gè)不相交的兩個(gè)相同長(zhǎng)寬的矩形就像不像在一塊布上剪下兩塊交換后縫好？
不難發(fā)現(xiàn)，如果能夠只在四邊進(jìn)行操作，而不在內(nèi)部每一個(gè)點(diǎn)上進(jìn)行轉(zhuǎn)換，時(shí)間復(fù)雜度會(huì)大大降低，但什么數(shù)據(jù)結(jié)構(gòu)能夠在 \(O(1)\) 的復(fù)雜度內(nèi)大面積交換呢？
如果是一維的轉(zhuǎn)換我們可以想到鏈表，那么二維轉(zhuǎn)換我們可以想到四向鏈表，在每次訪問(wèn)時(shí)只需要修改四周指向的位置，時(shí)間復(fù)雜度就減下來(lái)了。
時(shí)間復(fù)雜度：\(O(q \times (n+m))\)。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=1e3+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
struct List {
ll left,right,up,down,val;
} lst[N*N];
ll n,m,q;
string a[N][N];
inline void insert(ll val) {
ll num=val%(m+2),numl=val/(m+2);
ll up=(numl-1)*(m+2)+num,down=(numl+1)*(m+2)+num,left=val-1,right=val+1;
lst[val]={left,right,up,down,val};
}
inline ll find(ll rt,ll sp) {
for(ll i=lst[rt].right;;i=lst[i].right) {
sp--;
if(!sp) {
return lst[i].val;
}
}
return 0;
}
inline void query(ll x,ll y,ll xl,ll yl,ll len,ll cl) {
ll num=find(x*(m+2),y),numl=find(xl*(m+2),yl);
ll kl=num,kll=numl;
for(ll i=1;i<=len;i++) {
ll p1=lst[kl].left,p2=lst[kll].left;
swap(lst[p1].right,lst[p2].right);
swap(lst[kl].left,lst[kll].left);
if(i==len) {
break;
}
kl=lst[kl].down,kll=lst[kll].down;
}
for(ll i=1;i<=cl;i++) {
ll p1=lst[kl].down,p2=lst[kll].down;
swap(lst[p1].up,lst[p2].up);
swap(lst[kl].down,lst[kll].down);
if(i==cl) {
break;
}
kl=lst[kl].right,kll=lst[kll].right;
}
for(ll i=1;i<=len;i++) {
ll p1=lst[kl].right,p2=lst[kll].right;
swap(lst[p1].left,lst[p2].left);
swap(lst[kl].right,lst[kll].right);
if(i==len) {
break;
}
kl=lst[kl].up,kll=lst[kll].up;
}
for(ll i=1;i<=cl;i++) {
ll p1=lst[kl].up,p2=lst[kll].up;
swap(lst[p1].down,lst[p2].down);
swap(lst[kl].up,lst[kll].up);
if(i==cl) {
break;
}
kl=lst[kl].left,kll=lst[kll].left;
}
}
inline void output(ll x) {
for(ll i=lst[x].right;i!=x+m+1;i=lst[i].right) {
ll xl=(lst[i].val)/(m+2),yl=(lst[i].val)%(m+2);
cout<<a[xl][yl]<<' ';
}
cout<<'\n';
}
inline void solve() {
cin>>n>>m>>q;
for(ll i=1;i<=m;i++) {
lst[(n+1)*(m+2)+i]={0,0,n*(m+2)+i,0,(n+1)*(m+2)+i};
lst[i]={0,0,0,m+2+i,i};
}
for(ll i=1;i<=n;i++) {
lst[i*(m+2)]={0,i*(m+2)+1,0,0,i*(m+2)};
lst[i*(m+2)+m+1]={i*(m+2)+m,0,0,i*(m+2)+m+1};
}
for(ll i=1;i<=n;i++) {
for(ll j=1;j<=m;j++) {
cin>>a[i][j];
insert(i*(m+2)+j);
}
}
while(q--) {
ll x,y,xl,yl,len,cl;
cin>>x>>y>>xl>>yl>>len>>cl;
query(x,y,xl,yl,len,cl);
}
for(ll i=1;i<=n;i++) {
output(i*(m+2));
}
}
praise_long_long main() {
// freopen("file.in","r",stdin);
// freopen("file.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
ll T=1;
// T=read();
while(T--) {
solve();
}
return 0;
}
/**/
D - 排列
事實(shí)上我們可以考慮先想一下簡(jiǎn)化版，假設(shè)每個(gè)約束條件為 \(b\) 強(qiáng)制在 \(a\) 的后面，\(c\) 強(qiáng)制在 \(b\) 的后面，與原題區(qū)別在于強(qiáng)制要求了 \(a,c\) 的順序。那么這道題就變成了拓?fù)渑判虻陌遄宇}，因?yàn)楸ＷC存在解，又給定了順序，因此直接拓?fù)浼纯伞?/p>
現(xiàn)在重新考慮一下這道題，由于每個(gè)約束條件 \(a,c\) 的地位一模一樣,因此我們將他們稱為 \(e\)，將 \(b\) 成為 \(m\)，此時(shí)一個(gè)約束條件的在序列中的出現(xiàn)情況共有3種：\(eem，eme，mee\) 但是只有第二種情況時(shí)該約束條件才會(huì)產(chǎn)生1的貢獻(xiàn)，由于三種條件太復(fù)雜，我們又發(fā)現(xiàn) \(mee\) 這種情況可以通過(guò)類似于剛才的拓?fù)渑判蛑苯犹^(guò)不會(huì)出現(xiàn)，也就是說(shuō)我們可以先保證每一個(gè) \(m\) 都不會(huì)在兩個(gè) \(e\) 都沒(méi)出現(xiàn)的時(shí)候出現(xiàn)。具體地，我們對(duì)于每一個(gè)條件，將兩個(gè) \(e\) 同時(shí)向 \(m\) 連邊，當(dāng)刪除其中一條邊時(shí)，同時(shí)刪除另一條，這樣雖然圖建出來(lái)可能有環(huán)，但題目保證有解，因此一定存在合法拓?fù)湫?，這樣刪邊也就能同時(shí)拆環(huán)了。
Code
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
using namespace std;
inline ll read() {
char x=getchar();
ll ans=0,f=1;
while(x<'0'||x>'9') {
if(x=='-') {
f*=(-1);
}
x=getchar();
}
while(x>='0'&&x<='9') {
ans*=10;
ans+=(x-'0');
x=getchar();
}
return ans*f;
}
inline void print(ll x) {
if(x<0) {
putchar('-');
x=-x;
}
if(x>=10) {
print(x/10);
putchar(x%10+'0');
}
else {
putchar(x+'0');
}
}
}
using namespace io;
const ll N=1e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
struct node {
ll al,bl,cl;
} a[N];
ll n,m,du[N],l=1,r,ans[N],vis[N];
vector<pll> g[N];
vector<ll> v[N];
queue<ll> q;
inline void tosort() {
for(ll i=1;i<=n;i++) {
if(!du[i]) {
q.push(i);
}
}
while(!q.empty()) {
ll d=q.front();
q.pop();
ll val1=0,val2=0;
for(auto it : g[d]) {
ll al=it.first,cl=it.second;
if(vis[al]&&vis[cl]) {
continue;
}
if(vis[al]) {
if(vis[al]<=l) {
val1++;
}
if(vis[al]>=r) {
val2++;
}
}
if(vis[cl]) {
if(vis[cl]<=l) {
val1++;
}
if(vis[cl]>=r) {
val2++;
}
}
}
for(auto it : v[d]) {
ll al=a[it].al,bl=a[it].bl,cl=a[it].cl;
if(vis[al]) {
if(!vis[bl]) {
if(vis[al]<=l) {
val2++;
}
if(vis[al]>=r) {
val1++;
}
}
}
if(vis[cl]) {
if(!vis[bl]) {
if(vis[cl]<=l) {
val2++;
}
if(vis[cl]>=r) {
val1++;
}
}
}
if(!vis[al]&&!vis[cl]) {
du[bl]--;
if(!du[bl]) {
q.push(bl);
}
}
}
if(val1>=val2) {
vis[d]=l;
l++;
}
else {
vis[d]=r;
r--;
}
if(l>r) {
break;
}
}
}
inline void solve() {
r=n=read(),m=read();
for(ll i=1;i<=m;i++) {
a[i]={read(),read(),read()};
v[a[i].al].push_back(i);
v[a[i].cl].push_back(i);
g[a[i].bl].push_back({a[i].al,a[i].cl});
du[a[i].bl]++;
}
tosort();
for(ll i=1;i<=n;i++) {
ans[vis[i]]=i;
}
for(ll i=1;i<=n;i++) {
print(ans[i]);
putchar(' ');
}
}
praise_long_long main() {
// freopen("permutation.in","r",stdin);
// freopen("permutation.out","w",stdout);
ll T=1;
// T=read();
while(T--) {
solve();
}
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)