A. Emotional Flutter
自己乱搞搞了\(50pts\)，以为自己的复杂度是\(O(n)\)，但其实已经接近\(O(W)\).
乱搞代码
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define ll long long int
#define ull unsigned ll
#define re register ll
#define lf double
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x);
#define Copy(x,y) memcpy(x,y,sizeof x);
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=5e5+51;
ll Ts,n,m,r,t,cnt,alls,print;
struct I { ll l,r,len,col; } p[N];
set<pair<ll,ll> > s;
inline void Pre(){
s.clear();
for(re i=0;i<=n+1;++i) p[i].l=0,p[i].r=0,p[i].col=0,p[i].len=0;
alls=0,cnt=0,print=0;
return ;
}
inline void Init(){
r=read(),t=read(),n=read(); ll temp=r-1,flag;
p[1].l=1; p[0].col=1; flag=((n&1)^1);
if(flag) --n;
for(re i=1;i<=n;++i){
temp+=read(); if(temp<=0) { temp+=r-1; continue; }
if(p[cnt].col!=((i&1)^1)) ++cnt;
p[cnt].len+=temp,p[cnt].col=(i&1)^1;
// if(p[cnt].col) p[cnt].len%=t;
p[cnt].r=p[cnt].l+p[cnt].len-1,p[cnt+1].l=p[cnt].r+1;
if(i&1) temp=1-r; else temp=r-1;
}
if(flag) read();
n=cnt;
for(re i=1;i<=n;++i){
alls+=p[i].len;
if((!p[i].col) and p[i].len>=t){
puts("NIE"); print=1;
}
// cout<<p[i].l<<' '<<p[i].r<<' '<<p[i].len<<' '<<p[i].col<<'\n';
}
// cout<<"\n\n";
return ;
}
inline void Work(){
if(print) return ;
s.insert(mp(0,t));
ll i=1,bz; pair<ll,ll> tmp,temp;
while(i<=n and s.size()){
// cout<<tmp.first<<' '<<tmp.second<<' '<<p[i].l<<' '<<p[i].r<<endl;
if(s.empty()){ puts("NIE"); return ; }
if(!p[i].col) { ++i; continue; }
tmp=*s.begin();
if(tmp.second>alls) { puts("TAK"); return ; }
if(p[i].l>tmp.second) { s.erase(tmp); continue; }
if(p[i].r<tmp.first) { ++i; continue; }
if(p[i].l>=tmp.first and p[i].r<=tmp.second){
bz=(tmp.second-p[i].r)/t+1;
temp.first=p[i].l+t*bz,temp.second=p[i].r+t*bz;
s.insert(temp); ++i;
continue;
}
if(tmp.first>=p[i].l and tmp.second<=p[i].r){
bz=(p[i].r-tmp.second)/t+1;
temp.first=tmp.first+t*bz,temp.second=tmp.second+t*bz;
s.insert(temp); s.erase(tmp);
continue;
}
if(p[i].l<=tmp.first and p[i].r<=tmp.second and p[i].r>=tmp.first){
bz=(tmp.second-p[i].r)/t+1;
temp.first=tmp.first+t*bz,temp.second=p[i].r+t*bz;
s.insert(temp); ++i;
continue;
}
if(tmp.first<=p[i].l and tmp.second<=p[i].r and tmp.second>=p[i].l){
bz=(p[i].r-tmp.second)/t+1;
temp.first=p[i].l+t*bz,temp.second=tmp.second+t*bz;
s.insert(temp); s.erase(tmp);
continue;
}
}
if(s.begin()==s.end()){
if((*s.end()).second>alls) puts("TAK");
else puts("NIE");
}
else{
if((*(--s.end())).second>alls) puts("TAK");
else puts("NIE");
}
return ;
}
signed main(){
Ts=read();
while(Ts--){
Pre();
Init(),Work();
}
return 0;
}
思路来自 MAX_QAQ
首先把脚的长度累计到黑块上.
对于长度\(\geq k\)的黑块，直接表明本题无解.
起点只有\(k\)个，每个黑块对于对于这些起点均有贡献,可以选择\(mod\ k\)计算.
A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define ll long long int
#define ull unsigned ll
#define re register ll
#define lf double
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x);
#define Copy(x,y) memcpy(x,y,sizeof x);
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=5e5+51;
ll Ts,n,m,r,t,cnt,alls;
struct I { ll l,r,len,col; } p[N];
pair<ll,ll> e[N];
inline void Pre(){
for(re i=0;i<=n+1;++i) p[i].l=0,p[i].r=0,p[i].col=0,p[i].len=0;
for(re i=0;i<=cnt+1;++i) e[i].first=0,e[i].second=0;
alls=0,cnt=0;
return ;
}
inline void Init(){
r=read(),t=read(),n=read(); ll temp=r-1,flag;
p[1].l=1; p[0].col=1; flag=((n&1)^1);
if(flag) --n;
for(re i=1;i<=n;++i){
temp+=read(); if(temp<=0) { temp+=r-1; continue; }
if(p[cnt].col!=((i&1)^1)) ++cnt;
p[cnt].len+=temp,p[cnt].col=(i&1)^1;
p[cnt].r=p[cnt].l+p[cnt].len-1,p[cnt+1].l=p[cnt].r+1;
if(i&1) temp=1-r; else temp=r-1;
}
if(flag) read(); n=cnt;
}
inline void Work(){
cnt=0; ll l,r;
for(re i=1;i<=n;++i){
if(!p[i].col){
if(p[i].len>=t) { puts("NIE"); return ; }
l=p[i].l%t,r=p[i].r%t;
if(l>r){
e[++cnt].first=0,e[cnt].second=r,
e[++cnt].first=l,e[cnt].second=t-1;
}
else e[++cnt].first=l,e[cnt].second=r;
}
}
sort(e+1,e+1+cnt); r=-1;
// for(re i=1;i<=cnt;++i) cout<<e[i].first<<' '<<e[i].second<<endl;
if(e[1].first!=0) {puts("TAK"); return ;}
for(re i=1;i<=cnt;i++){
if(e[i].first>r+1){
puts("TAK"); return ;
}
else{
r=max(e[i].second,r);
}
}
if(r<t-1) puts("TAK");
else puts("NIE");
return;
}
signed main(){
Ts=read();
while(Ts--){
Pre();
Init(),Work();
}
return 0;
}