T1
简单暴搜判断答案
#include<bits/stdc++.h>
const int N=15;
using namespace std;
int n,a[N][N],now[N],ans;
inline int dist(int a,int b){
return a<=b?b-a:b-a+10;
}
inline int check(int x){
int cnt=0,lst=0;
for(int i=1;i<=5;++i)
if(now[i]!=a[x][i]){
if(++cnt>2) return 1;
if(cnt==1){
lst=i;
continue;
}
if(lst!=i-1) return 1;
if(dist(a[x][i-1],now[i-1])!=dist(a[x][i],now[i])) return 1;
}
return cnt==0;
}
inline void calc(){
for(int i=1;i<=n;++i)
if(check(i)) return;
++ans;
}
void dfs(int x){
if(x>5) return calc();
for(int i=0;i<10;++i)
now[x]=i,dfs(x+1);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i][1]>>a[i][2]>>a[i][3]>>a[i][4]>>a[i][5];
dfs(1);
cout<<ans<<endl;
}
T2
哈希，维护前缀栈的形态，相同说明可以消除。
场上哈希被卡了，交了暴力 /kk
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=2e6+5,base1=237,base2=239;
int T,n;
int st[N],top;
int pw1[N],pw2[N];
char a[N];
map<pair<ull,ull>,int>mp;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>a+1,pw1[0]=pw2[0]=1;
for(int i=1;i<N;++i)
pw1[i]=pw1[i-1]*base1,
pw2[i]=pw2[i-1]*base2;
mp[{0ull,0ull}]++;
ull ans=0,val1=0,val2=0;
for(int i=1;i<=n;++i){
if(top&&a[st[top]]==a[i]) val1-=a[i]*pw1[top],val2-=a[i]*pw2[top],--top;
else st[++top]=i,val1+=a[i]*pw1[top],val2+=a[i]*pw2[top];
ans+=mp[{val1,val2}]++;
}
cout<<ans<<endl;
}
T3
恶臭大模拟，场上使用 \(\text{yn}\) 做变量名 CE 了，挂了 \(70pts\) /kk
// Problem: P9754 [CSP-S 2023] 结构体【民间数据】
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9754?contestId=140859
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
using namespace std;
const int N=1e5+5;
string s1[5]={"byte","short","int","long"};
int sz[N]={1,2,4,8};
inline int St(int now,int d){
return (now+d-1)/d*d;
}
struct node{
vector<pair<string,pair<int,int> > >son;
int mx,sz;
}S[N];
int nam;
map<string,int>mp;
string s,tmpt[N],tmpn[N];
inline void addstr(){
int k;
cin>>s>>k;
mp[s]=++nam;
for(int i=1;i<=k;++i){
cin>>tmpt[i]>>tmpn[i];
S[nam].mx=max(S[nam].mx,S[mp[tmpt[i]]].mx);
}
int now=0;
for(int i=1;i<=k;++i){
int id=mp[tmpt[i]];now=St(now,S[id].mx);
S[nam].son.push_back(mp(tmpn[i],mp(id,now))),now+=S[id].sz;
}
S[nam].sz=St(now,S[nam].mx);
cout<<S[nam].sz<<" "<<S[nam].mx<<endl;
}
vector<pair<pair<int,int>,string> >ys;
int Now;
string Yn;
inline void addys(){
cin>>s>>Yn;
int id=mp[s];
Now=St(Now,S[id].mx);
cout<<Now<<endl;
ys.push_back(mp(mp(id,Now),Yn));
Now+=S[id].sz;
}
inline void find(){
cin>>s;
int len=s.size(),i=0;
string now="";
for(i=0;i<len;++i)
if(s[i]=='.') break;
else now+=s[i];
int ans=0,Id;
for(auto x:ys)
if(x.sec==now){
ans=x.fir.sec,Id=x.fir.fir;
while(i<len){
now="";
for(++i;i<len;++i)
if(s[i]=='.') break;
else now+=s[i];
for(auto y:S[Id].son)
if(y.fir==now){
ans+=y.sec.sec,Id=y.sec.fir;
break;
}
}
cout<<ans<<endl;
return;
}
}
string res[N];
inline void addr(){
int sum,cnt=0;
cin>>sum;
if(sum>=Now) return cout<<"ERR"<<endl,void();
for(int p=1;p<(int)ys.size();++p){
pair<pair<int,int>,string> y=ys[p];
if(y.fir.sec>sum){
y=ys[p-1],sum-=y.fir.sec,res[++cnt]=y.sec;
int Id=y.fir.fir;
if(S[Id].sz<=sum) return cout<<"ERR"<<endl,void();
while(1){
if(Id<=4){
for(int i=1;i<cnt;++i) cout<<res[i]<<".";
cout<<res[cnt]<<endl;
return;
}
auto x=S[Id].son[S[Id].son.size()-1];
if(x.sec.sec+S[x.sec.fir].sz<=sum) return cout<<"ERR"<<endl,void();
else if(x.sec.sec<=sum){
res[++cnt]=x.fir;
sum-=x.sec.sec,Id=x.sec.fir;
if(Id<=4){
for(int i=1;i<cnt;++i) cout<<res[i]<<".";
cout<<res[cnt]<<endl;
return;
}
continue;
}
for(int p=0;p<(int)S[Id].son.size()-1;++p){
auto x=S[Id].son[p];
if(x.sec.sec<=sum&&S[Id].son[p+1].sec.sec>sum){
if(x.sec.sec+S[x.sec.fir].sz<=sum) return cout<<"ERR"<<endl,void();
sum-=x.sec.sec,Id=x.sec.fir,
res[++cnt]=x.fir;
break;
}
}
if(Id<=4){
for(int i=1;i<cnt;++i) cout<<res[i]<<".";
cout<<res[cnt]<<endl;
return;
}
}
}
}
pair<pair<int,int>,string> y=ys[ys.size()-1];
sum-=y.fir.sec,res[++cnt]=y.sec;
int Id=y.fir.fir;
if(S[Id].sz<=sum) return cout<<"ERR"<<endl,void();
while(1){
if(Id<=4){
for(int i=1;i<cnt;++i) cout<<res[i]<<".";
cout<<res[cnt]<<endl;
return;
}
auto x=S[Id].son[S[Id].son.size()-1];
if(x.sec.sec+S[x.sec.fir].sz<=sum) return cout<<"ERR"<<endl,void();
else if(x.sec.sec<=sum){
res[++cnt]=x.fir;
sum-=x.sec.sec,Id=x.sec.fir;
if(Id<=4){
for(int i=1;i<cnt;++i) cout<<res[i]<<".";
cout<<res[cnt]<<endl;
return;
}
continue;
}
for(int p=0;p<(int)S[Id].son.size()-1;++p){
auto x=S[Id].son[p];
if(x.sec.sec<=sum&&S[Id].son[p+1].sec.sec>sum){
if(x.sec.sec+S[x.sec.fir].sz<=sum) return cout<<"ERR"<<endl,void();
sum-=x.sec.sec,Id=x.sec.fir,
res[++cnt]=x.fir;
break;
}
}
if(Id<=4){
for(int i=1;i<cnt;++i) cout<<res[i]<<".";
cout<<res[cnt]<<endl;
return;
}
}
}
int opt,n;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i<4;++i) mp[s1[i]]=++nam,S[nam].sz=S[nam].mx=sz[i];
while(n--){
cin>>opt;
if(opt==1) addstr();
else if(opt==2) addys();
else if(opt==3) find();
else addr();
}
}
T4
简单贪心，二分答案，然后得到每个数最晚时间，按 \(\text{lim}\) 排序后模拟即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int n;
int a[maxn],b[maxn],c[maxn],lim[maxn],f[maxn];
vector<int>g[maxn];
int vis[maxn];
void dfs(int u,int fa){
f[u]=fa;
for(auto v:g[u])
if(v!=fa) dfs(v,u);
}
const __int128 I=1;
inline __int128 calct(int i,int T){
if(c[i]>=0) return I*T*b[i]+I*c[i]*(T*T+T)/2;
int pos=(b[i]-1)/(-c[i]);
if(T<=pos)return I*T*b[i]+I*c[i]*(T*T+T)/2;
else return I*pos*b[i]+I*c[i]*(pos*pos+pos)/2+(T-pos);
}
int per[maxn],now[maxn],tp=0;
vector<int>t[maxn];
inline bool check(int x){
for(int i=1;i<=n;i++){
int l=1,r=x,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(calct(i,x)-calct(i,mid-1)>=a[i])ans=mid,l=mid+1;
else r=mid-1;
}
if(ans==-1)return 0;
lim[i]=min(n+1,ans);
}
for(int i=1;i<=n;i++)vis[i]=0;
for(int i=0;i<=n+1;i++)t[i].clear();
for(int i=1;i<=n;i++)t[lim[i]].push_back(i);
int F=1,T=0;
for(int i=0;i<=n+1;i++)
for(auto u:t[i])per[++F]=u;
for(int i=1,op;i<=n;i++){
if(i==1)op=1;
else op=per[i];
tp=0;
while(op&&!vis[op])
now[++tp]=op,op=f[op];
for(int j=tp;j>=1;j--){
int x=now[j];
vis[x]=1;
if(++T>lim[x])return 0;
}
}
return 1;
}
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=read(),c[i]=read();
for(int i=1,u,v;i<n;i++)
u=read(),v=read(),g[u].push_back(v),g[v].push_back(u);
dfs(1,0);
int L=n,R=1e9,ans=114514;
while(L<=R){
int mid=(L+R)>>1;
if(check(mid)) R=mid-1,ans=mid;
else L=mid+1;
}
cout<<ans<<endl;
return 0;
}