QLU校赛

QLU校赛

as a tester，problems are good and I recommend participating

验题是几周前的事情了，只能凭借印象口胡两下

B.新大陆

暴力，复杂度O(n*m)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
using ll=long long;
vector<ll>g[N];
vector<int>st[N];bool check(int p1,int p2,int &h,int &w)
{for(int i=p1;i<=p1+h-1;++i){for(int j=p2;j<=p2+w-1;++j){if(g[i][j]!=g[p1][p2])return false;st[i][j]=1;}}return true;
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)g[i].resize(m+1),st[i].resize(m+1);for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%lld",&g[i][j]);int h,w;scanf("%d%d",&h,&w);for(int i=1;i<=n-h+1;++i)for(int j=1;j<=m-w+1;++j){if(st[i][j])continue;if(check(i,j,h,w)){printf("YES\n");return 0;}}for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)st[i][j]=0;for(int i=1;i<=n-w+1;++i)for(int j=1;j<=m-h+1;++j){if(st[i][j])continue;if(check(i,j,w,h)){printf("YES\n");return 0;}}printf("NO\n");return 0;
}

C

勇者之塔，考虑下边界

#include<bits/stdc++.h>
using namespace std;
using ll=long long;int main()
{ll n,m;cin>>n>>m;int T;scanf("%d",&T);while(T--){int x,y,k;scanf("%d%d%d",&x,&y,&k);if(!x&&!y){printf("1 1 1\n");continue ;}int t=min((x>0?((n+x-1)/x):0x3f3f3f3f),(y>0?((m+y-1)/y):0x3f3f3f3f));int rs1=1+k/t;k=k%t;int rs2=x*k+1,rs3=y*k+1;printf("%d %d %d\n",rs1,rs2,rs3);}
}

D  史莱姆

发现n*m<1e6考虑n<1e3或者m<1e3

所以有1e3个优先队列

复杂度 O(min(n,m)*p*log(m));大概这样？忘了

不过有去掉log的更优解，当然，写线段树也是很好想的东西

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
using ll=long long;
vector<vector<pair<int,int>>> e[N];
vector<int>w[N];
int aa,bb;
int col[N];
int f(int i)
{return col[i]*aa+bb;
}
// if n<=m
void solve1(int n,int m,int p,int c)
{for(int i=1;i<=n;++i)e[i].resize(m+1),w[i].resize(m+1);for(int i=1;i<=c;++i)scanf("%d",&col[i]);unordered_map<int,int> mp;for(int i=1;i<=c;++i)mp[f(i)]=i;mp[0]=0;while(p--){int x1,y1,x2,y2,c1;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c1);for(int i=x1;i<=x2;++i)e[i][y1].push_back({f(c1),y2});}for(int i=1;i<=n;++i){priority_queue<pair<int,int>> heap;for(int j=1;j<=m;++j){for(auto v:e[i][j])heap.push(v);while((int)heap.size()&&heap.top().second<j)heap.pop();if((int)heap.size())w[i][j]=mp[max(heap.top().first,0)];}}for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)printf("%d%c",w[i][j]," \n"[j==m]);
}void solve2(int n,int m,int p,int c)
{for(int i=1;i<=m;++i)e[i].resize(n+1),w[i].resize(n+1);for(int i=1;i<=c;++i)scanf("%d",&col[i]);unordered_map<int,int> mp;for(int i=1;i<=c;++i)mp[f(i)]=i;mp[0]=0;while(p--){int x1,y1,x2,y2,c1;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c1);for(int i=y1;i<=y2;++i)e[i][x1].push_back({f(c1),x2});}for(int i=1;i<=m;++i){priority_queue<pair<int,int>> heap;for(int j=1;j<=n;++j){for(auto v:e[i][j])heap.push(v);while((int)heap.size()&&heap.top().second<j)heap.pop();if((int)heap.size())w[i][j]=mp[max(heap.top().first,0)];}}for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)printf("%d%c",w[j][i]," \n"[j==m]); 
}
int main()
{int n,m,p,c;scanf("%d%d%d%d%d%d",&n,&m,&p,&c,&aa,&bb);if(n<=m)solve1(n,m,p,c);else solve2(n,m,p,c);
}

E 贴贴

考虑到质数是稠密的，并且平均log个数就有一个，所以平均会在log内求的所需值，上下边界求一下取min

#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
using ll=long long;
const int N=1e7+10;
int pri[N],cnt;
bool st[N];
void init()
{for(int i=2;i<N;++i){if(!st[i])pri[++cnt]=i;for(int j=1;pri[j]*i<N;++j){st[pri[j]*i]=1;if(i%pri[j]==0)break;}}
}
bool check(ll n)
{for(int i=1;i<=cnt;++i){if(n==1)break;if(n%pri[i]==0){if(n%(1ll*pri[i]*pri[i])==0)return 0;n/=pri[i];//cout<<"ss "<<pri[i]<<endl;}}return 1;
}
ll up(ll n)
{while(n)if(!check(n))++n;else return n;
}
ll down(ll n)
{while(n)if(!check(n))--n;else return n;
}
int main()
{init();ll n;cin>>n;ll rs_up=up(n);ll rs_down=down(n);if(rs_down==rs_up){cout<<n<<endl;return 0;}if(n-rs_down<=rs_up-n)cout<<rs_down<<'\n';if(n-rs_down>=rs_up-n)cout<<rs_up<<endl;
}

F 时间就是金钱

虚树，队友说很板？但我不会

#include <iostream> /// 洛谷 4103 每次询问点集合中各点之间 1.路径长度总和 2.最短路径长度 3.最长路径长度
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int N=100005;
struct pp
{int to;int old;
}edge[N*2];
int newly[N],cnt;
int dep[N],lg[N],f[N][25],dfn[N],dfn_cnt;
int ss[N],top,flag[N];
vector<pair<int, int> >a;
int vvv[N];
long long down[N],dp[N],ans;
int sz[N];void add(int u, int v)
{edge[cnt]={v, newly[u]};newly[u]=cnt++;
}void dfs(int x, int fa)
{dfn[x]=++dfn_cnt;dep[x]=dep[fa]+1;f[x][0]=fa;for(int i=1; i<=lg[dep[x]]; i++)f[x][i]=f[f[x][i-1]][i-1];for(int i=newly[x]; ~i; i=edge[i].old)if(edge[i].to!=fa)dfs(edge[i].to, x);
}int lca(int x, int y)
{if(dep[x]<dep[y])swap(x, y);while(dep[x]>dep[y])x=f[x][lg[dep[x]-dep[y]]-1];if(x==y) return x;for(int k=lg[dep[x]]-1; k>=0; k--)if(f[x][k]!=f[y][k])x=f[x][k],y=f[y][k];return f[x][0];
}void down_dfs(int x, int fa)
{
//	cout << x << '\n';sz[x]=vvv[x];for(int i=newly[x]; ~i; i=edge[i].old){int son=edge[i].to,w=dep[son]-dep[x];if(son==fa)continue;down_dfs(son, x);sz[x]+=sz[son];down[x]+=down[son]+1ll*w*sz[son];}
}void ans_dfs(int x, int fa)
{ans=min(ans, dp[x]);for(int i=newly[x]; ~i; i=edge[i].old){int son=edge[i].to,w=dep[son]-dep[x];if(son==fa)continue;dp[son]=dp[x]-down[son]-1ll*w*sz[son]+1ll*(sz[1]-sz[son])*w+down[son];ans_dfs(son, x);}
}void init_dfs(int x, int fa)
{for(int i=newly[x]; ~i; i=edge[i].old){if(edge[i].to==fa)continue;init_dfs(edge[i].to, x);}newly[x]=-1,flag[x]=0,dp[x]=0,down[x]=0,sz[x]=0,vvv[x]=0;
}int main()
{int n,q;memset(newly,-1,sizeof(newly));scanf("%d%d", &n, &q);for(int i=1; i<=n; i++)lg[i]=lg[i>>1]+1;for(int i=1; i<n; i++){int x,y;scanf("%d%d", &x, &y);add(x, y),add(y, x);}dfs(1, 0);memset(newly,-1,sizeof(newly));
//	cout << "------" << '\n';while(q--){int m; scanf("%d", &m);a.clear(),top=cnt=0;int k; scanf("%d", &k);for(int i=1; i<=k; i++){int x; scanf("%d", &x);vvv[x]++;if(flag[x])continue;flag[x]=1;a.push_back({dfn[x], x});}int cc=1; // 默认根节点入栈if(!flag[cc])a.push_back({dfn[cc], cc});sort(a.begin(), a.end());ss[++top]=cc;for(int i=1; i<a.size(); i++){int now=a[i].second;if(top==1)ss[++top]=now;else{int p=lca(now, ss[top]);if(p==ss[top])ss[++top]=now;else{while(top>1 && dfn[p]<=dfn[ss[top-1]])add(ss[top-1], ss[top]),top--;if(p!=ss[top])add(p, ss[top]),ss[top]=p;ss[++top]=now;}}}while(top>1)add(ss[top-1], ss[top]),top--;ans=m;down_dfs(cc, -1);dp[cc]=down[cc];ans_dfs(cc, -1);
//		cout << " size : " << a.size() << '\n';
//		for(int i=0; i<a.size(); i++)
//			if(flag[a[i].second])
//				cout << a[i].second << " : " << dp[a[i].second] << "  ---- ";
//		cout << '\n';if(ans==m)cout << "Good game" << '\n';elsecout << ans << '\n';init_dfs(cc, -1);}return 0;
}

G 简单的数学

很容易发现化简后就是n

#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
using ll=long long;int main()
{int n;cin>>n;cout<<n<<endl;
}

H L的子序列

很一眼的树状数组维护DP

#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7;
using ll=long long;
const int N=1e5+10;
template<typename T> struct BIT
{ll tr[N];T query(int x){T res=0;for(;x;x-=x&-x)res+=tr[x];return res;}void modify(int x,T y){for(;x<N;x+=x&-x)tr[x]+=y;}T cal(int l,int r){return query(r)-query(l-1);}
};
using Bit=BIT<ll>;ll dp[N],f[N];
Bit bit_dp,bit_f;
void add(ll &a,ll b)
{a+=b;if(a>=P)a-=P;
}
int main()
{int n;scanf("%d",&n);vector<ll> a(n+1);for(int i=1;i<=n;++i)scanf("%lld",&a[i]);vector<ll> b(n);for(int i=1;i<=n;++i)b[i-1]=a[i];sort(b.begin(),b.end());map<ll,int> mp;mp[-1]=0;int cnt=0;for(int i=1;i<=n;++i)if(mp.find(b[i-1])==mp.end())mp[b[i-1]]=++cnt;;for(int i=1;i<=n;++i){ll t=a[i]/2;ll pos=mp[a[i]];add(dp[i],1);add(f[i],1);auto p1=mp.upper_bound(t);--p1;// if(p1!=mp.begin())// {add(dp[i],bit_dp.query(p1->second)%P);// cout<<"now is p1: "<<(p1->second)<<endl;// cout<<"i--> "<<i<<" dp[i]-->"<<dp[i]<<endl;add(f[i],(bit_f.query(p1->second))%P);bit_dp.modify(pos,dp[i]);bit_f.modify(pos,(f[i]+dp[i])%P);// }}ll rs=0;// for(int i=1;i<=n;++i)printf("%lld%c",dp[i]," \n"[i==n]);// for(int i=1;i<=n;++i)printf("%lld%c",f[i]," \n"[i==n]);for(int i=1;i<=n;++i)add(rs,f[i]);cout<<rs<<endl;
}

I 秋游

感觉以前写过吧，做几遍dijkstra之后状压

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
using pli=pair<ll,int>;
using pii=pair<int,int>;
vector<pii> e[N];
ll dist[N];
ll dis[30][30];
ll dp[1<<20][20];
void dijkstra(int root)
{memset(dist,0x3f,sizeof(dist));dist[root]=0;priority_queue<pli,vector<pli>,greater<pli>>heap;heap.push({0,root});while(heap.size()){auto [val,u]=heap.top();heap.pop();for(auto [v,w]:e[u]){if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;heap.push({dist[v],v});}}}
}
int main()
{int n,x,y;scanf("%d%d%d",&n,&x,&y);vector<int>spots(x);for(auto &v:spots)cin>>v;int m;scanf("%d",&m);for(int i=1,u,v,w;i<=m;++i)scanf("%d%d%d",&u,&v,&w),e[u].push_back({v,w}),e[v].push_back({u,w});dijkstra(1);for(int i=1;i<=x;++i)dis[0][i]=dist[spots[i-1]];for(int i=1;i<=x;++i){dijkstra(spots[i-1]);for(int j=1;j<=x;++j)dis[i][j]=dist[spots[j-1]];dis[i][0]=dist[1];}memset(dp,0x3f,sizeof(dp));dp[1][0]=0;for(int i=1;i<1<<x+1;++i){for(int j=0;j<=x;++j){if(i&1<<j)for(int k=0;k<=x;++k){dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+dis[j][k]);}}}ll rs=1e18;for(int i=0;i<1<<x+1;++i){if(__builtin_popcount(i)!=y+1)continue;for(int j=0;j<=x;++j)rs=min(rs,dp[i][j]+dis[j][0]);}//cout<<dis[2][1]<<'\n';cout<<rs<<'\n';
}

J 串串大师

队友写的，不予评价

void init()
{last=0;len[1]=-1;s[0]='?';fail[0]=fail[1]=1;
}int get_fail(int x)
{while(s[ni-len[x]-1]!=s[ni])x=fail[x];return x;
}void add(int c, int idx)
{int old=get_fail(last);  if(!pam[old][c]) // {int now=++pam_cnt;fail[now]=pam[get_fail(fail[old])][c];pam[old][c]=now;len[now]=len[old]+2;for(int j=0; j<26; j++)mm_cnt[now][j]=mm_cnt[old][j];mm_cnt[now][c]++;if(len[now]!=1)mm_cnt[now][c]++;}last=pam[old][c];cnt[last]++;
}void count() 
{for(int i=pam_cnt; i>=2; i--)(cnt[fail[i]]+=cnt[i])%=mod;
}signed main()
{pam_cnt=1;int k,n;scanf("%lld", &k);for(int i=1; i<=k; i++){scanf("%s", s+1);init();n=strlen(s+1);for(ni=1; ni<=n; ni++)add(s[ni]-'a', i);}count();long long ans=0;for(int i=2; i<=pam_cnt; i++){long long res=1;for(int j=0; j<26; j++)if(mm_cnt[i][j])res=res*mm_cnt[i][j]%mod;
//		cout << len[i] << " : " << res << '\n';ans=(ans+res*cnt[i]%mod)%mod;}cout << ans << '\n';return 0;
}

K L的树

队友写的，不予评价

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N=100005;
struct seg_tree
{int tree[N<<2];void push_up(int p){tree[p]=tree[p<<1]+tree[p<<1|1];}void modify(int p, int tl, int tr, int dis, int v){if(tl==tr){tree[p]+=v;return ;}int mid=(tl+tr)>>1;if(dis<=mid)modify(p<<1, tl, mid, dis, v);elsemodify(p<<1|1, mid+1, tr, dis, v);push_up(p);}int query(int p, int l, int r, int dl, int dr){if(l>=dl && r<=dr) // 被目标区间包含 立即返回答案return tree[p];int mid=(l+r)>>1;int ans=0;if(dl<=mid)ans+=query(p<<1, l, mid, dl, dr);if(dr>mid)ans+=query(p<<1|1, mid+1, r, dl, dr);return ans;}
}T[11];
struct pp
{int to;int old;
}edge[N<<1];
int newly[N],cnt;
int dfn[N],out[N],dfn_cnt;
int now[N];
void add(int u, int v)
{edge[cnt]={v, newly[u]};newly[u]=cnt++;
}void dfs(int x, int fa)
{dfn[x]=++dfn_cnt;for(int i=newly[x]; ~i; i=edge[i].old){int to=edge[i].to;if(to==fa)continue;dfs(to, x);}out[x]=dfn_cnt;
}
int uu[N],ans[20];
bool cmp(int x, int y)
{return dfn[x]<dfn[y];
}int main()
{memset(newly,-1,sizeof(newly));int n,q; scanf("%d%d", &n, &q);for(int i=1; i<n; i++){int u,v;scanf("%d%d", &u, &v);add(u, v),add(v, u);}dfs(1, -1);for(int i=1; i<=n; i++){int c; scanf("%d", &c);now[i]=c;T[c].modify(1, 1, dfn_cnt, dfn[i], 1);}
//	for(int i=1; i<=n; i++)
//		cout << dfn[i] << ' ';
//	cout << '\n';
//	cout << T[1].query(1, 1, dfn_cnt, dfn[2], out[2]) << '\n';while(q--){int op; scanf("%d", &op);if(op==1){int x,y; scanf("%d%d", &x, &y);T[now[x]].modify(1, 1, dfn_cnt, dfn[x], -1);T[y].modify(1, 1, dfn_cnt, dfn[x], 1);now[x]=y;}else{for(int i=1; i<=10; i++)ans[i]=0;int m; scanf("%d", &m);for(int i=1; i<=m; i++)scanf("%d", &uu[i]);sort(uu+1, uu+1+m, cmp);
//			cout << "排序后为 : ";
//			for(int i=1; i<=m; i++)
//				cout << uu[i] << ' ';
//			cout << '\n';int pre=-1;for(int i=1; i<=m; i++){if(dfn[uu[i]]<=pre)continue;pre=out[uu[i]];for(int j=1; j<=10; j++)ans[j]+=T[j].query(1, 1, dfn_cnt, dfn[uu[i]], out[uu[i]]);}for(int i=1; i<=10; i++)cout << ans[i] << " \n"[i==10];}}return 0;
}

K 奥特曼的时间管理

写模拟一点也不拿手啊，感觉得加把油了

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
ll x,y,z;
ll get(char a, char b)
{return (a-'0')*10+b-'0';
}
ll cal(ll a,ll b,ll c)
{// ll tmp=c/z;// c%=z;// b+=tmp;// tmp=b/y;b%=y;a+=tmp;return a*y*z+b*z+c;
}
int main()
{ll n,k,val;cin>>n>>x>>y>>z>>k>>val;vector<pll> q;for(int i=1;i<=n;++i){string str;cin>>str;ll t1=cal(get(str[0],str[1]),get(str[3],str[4]),get(str[6],str[7]));cin>>str;ll t2=cal(get(str[0],str[1]),get(str[3],str[4]),get(str[6],str[7]));q.push_back({t1,t2});// cout<<t1<<" "<<t2<<endl;}sort(q.begin(),q.end());ll rs=0,lst=q[0].first-1;ll N=cal(x-1,y-1,z-1);for(auto [S,T]:q){if(T>N)T=N;if(T<lst)continue;if(S<=lst&&T>lst){rs+=T-lst;lst=T;}else if(S>=lst&&S<=lst+k){rs+=T-lst;lst=T;}else if(S>lst+k){rs+=T-S+1+k;lst=T;// cout<<S<<" "<<T<<" "<<rs<<endl;}}rs+=min(k,N-lst);cout<<rs*val<<endl;// cout<<(4793-4733+4733-4710+1)*2;
}