2024.7.12 IOI赛制欢乐赛总结
__Floyd__
·
2024-07-12 17:40:21
·
个人记录
本蒟蒻已哭晕在厕所
Part 1 赛前-------------------------
赛前一天就是\textcolor{purple}{划水，划水，再划水！}
简单整理了一下刚刚学过的Kmp,Tarjan和树状数组板子 （虽然还是不很会qwq ），当然树上倍增求LCA 也是必要整理的。
毕竟学了这么久这些东西还没有完全掌握，万一考了就只能乖乖躺在棺材上被某大佬 膜拜 ）直接一波送走。
其他什么DFS，BFS，Spfa，Dijkstra, 就先放一边， 好像很会的样子
Part 2 赛时-------------------------
概括
整个比赛还是很紧张的，没什么时间去想其他，全神贯注投入，虽然状态还说得过去，但是————又崩了。
具体怎样，请听我慢慢道来：
时间安排
赛后总结-------------------------
表现总结
本次比赛表现平平（烂极了 ），总分只有\textcolor{green}{310pts} （我是蒟蒻 ），T1 ，T2 ，T4 和T5 的 一部分极少 ）分数，该打的暴力都没有打，例如T6 的DFS \textcolor{brown}{40pts} ，（T3 暴力不会打就不说了），总之，就一个字
“烂” 题目总结
T1 签到题，求解满足各位数字均不相同的1位数~10位数，想写特判 写特判 ，想写循环 写循环
T2 同样也是签到题，挺简单，用四个前缀和数组，加上O(n^2) 的子串左右端点枚举，很轻松就可以过啦
T3 排列组合题 ，可以很直观看出，对于每一个k ，方案数为每一个{a_i \choose k} 相乘，但是这样复杂度是O(nm) 的，明显会\textcolor{red}{TLE} 。再细看，我们能够发现，\displaystyle\sum_{i=1}^n a_i\le 10^{5} 这个限制条件使得a_i 中不相同的个数非常少，约为500个，那么我们可以考虑对a 数组排序后去重 ，再运用快速幂 和逆元 ，就可以把算法的时间复杂度优化到O(500m) ，从而通过此题
T4
### [**T5**](http://172.20.0.170/d/summer/p/673)
**贪心**，没错，就是**greedy**，它又出场了。
首先，我们能够想到，如果有能够配对的$(2,4),(3,3)$数对，那么先进行配对一定是最优的。
其次，我们进一步拓展。如果目前存在能够配对的$(x,5)$数对，那么进行配对也是最优的，而且$x$应该从小到大枚举，满足最优
在者，我们再深一步。如果存在$(x,2,3),(x,y,4)$这样的数对，优先结合也是最优的。
最后，我们统计$(1,2,3)$即可
**（不懂见文末代码（当然不是我的））**
### [**T6**](http://172.20.0.170/d/summer/p/672)
考虑建立多层图，为什么呢？注意数据范围——$W\le500$，那么我们可以考虑让第$i$层图表示最大$gcd$为$i$时的无向图，从任意一个节点$x$到节点$n$的最短路由$dis_{i,x}$来统计，
每一层跑一个**单源最短路径**（$n$为出发点），查询点$a$时在$\displaystyle\sum_{i=1}^W dis_{i,a}$中取$max$并输出即可
# 代码STD
* T1
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll read(){
ll x;scanf("%lld",&x);return x;
}
ll n,m;
int main(){
// freopen("A.in","r",stdin);
// freopen("A.out","w",stdout);
n=read();
if(n==1) cout<<1;
else if(n==2) cout<<10;
else if(n==3) cout<<102;
else if(n==4) cout<<1023;
else if(n==5) cout<<10234;
else if(n==6) cout<<102345;
else if(n==7) cout<<1023456;
else if(n==8) cout<<10234567;
else if(n==9) cout<<102345678;
else if(n==10) cout<<1023456789;
else cout<<(-1);
return 0;
}
```
* T2
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x;scanf("%lld",&x);return x;
}
const ll N=1e6+10;
ll n;
string s;
ll sumA[N],sumT[N],sumG[N],sumC[N],ans=0;
int main(){
// freopen("B.in","r",stdin);
// freopen("B.out","w",stdout);
n=read();
cin>>s;
for(int i=0;i<n;i++){
sumA[i+1]=sumA[i];
sumT[i+1]=sumT[i];
sumG[i+1]=sumG[i];
sumC[i+1]=sumC[i];
if(s[i]=='A') sumA[i+1]++;
else if(s[i]=='G') sumG[i+1]++;
else if(s[i]=='T') sumT[i+1]++;
else sumC[i+1]++;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(sumA[j]-sumA[i-1]==sumT[j]-sumT[i-1]&&sumG[j]-sumG[i-1]==sumC[j]-sumC[i-1]){
ans++;
}
}
}
cout<<ans;
return 0;
}
```
* T3
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <cassert>
#include <cstdlib>
#define pii pair<int,int>
#define mp make_pair
#define pb emplace_back
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned long long ull;
const int DMAX = 200000 + 5;
const double INF = 1e9;
const int MOD = 998244353;
using namespace std;
template<class T> inline void read(T &x){
T f=1; x=0; char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9' && ch>='0'){ x=x*10+ch-'0';ch=getchar(); }
x*=f;
}
int qpow(int a,int b,int p){
int t=1;
while(b){
if(b&1){
t=1ll*t*a%p;
}
a=1ll*a*a%p;
b>>=1;
}
return t;
}
int n,m;
int a[DMAX];
int ans;
int jc[DMAX],jcinv[DMAX];
int ma[DMAX];
vector<int> vec;
int C(int a,int b){
if(a<b){
return 0;
}
return 1ll*jc[a]*jcinv[b]%MOD*jcinv[a-b]%MOD;
}
int main(){
read(n),read(m);
int res=0;
for(int i=1;i<=n;i++){
read(a[i]);
res+=a[i];
ma[a[i]]++;
if(ma[a[i]]==1){
vec.pb(a[i]);
}
}
assert(res<=100000);
jc[0]=jcinv[0]=1;
for(int i=1;i<=100000;i++){
jc[i]=1ll*jc[i-1]*(ll)i%MOD;
}
jcinv[100000]=qpow(jc[100000],MOD-2,MOD);
for(int i=100000-1;i>=1;i--){
jcinv[i]=1ll*jcinv[i+1]*(i+1)%MOD;
}
for(int i=1;i<=m;i++){
ans=1;
for(auto v:vec){
ans=1ll*ans*qpow(C(i,v),ma[v],MOD)%MOD;
}
printf("%d ",ans);
}
puts("");
return 0;
}
```
* T4
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e7+10;
ll read(){
ll x;scanf("%lld",&x);return x;
}
ll t,n,a[N],b[N];
bool check(ll x){
priority_queue<ll>q;
ll sa=0,sb=0,nowa=x,nowb=x;
for(int i=1;i<=n;i++){
// cout<<q.size()<<endl;
sa+=a[i],sb+=b[i];
q.push(1);
while(nowa<sa&&q.size()){
nowa+=1;
q.pop();
}
if(nowa<sa) return 0;
while(nowb<sb&&q.size()){
nowb+=1;
q.pop();
}
if(nowb<sb) return 0;
}
return 1;
}
int main(){
// freopen("D.in","r",stdin);
// freopen("D.out","w",stdout);
t=read();
while(t--){
n=read();
for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();
ll l=0,r=2e5,mid;
while(l<r){
mid=(l+r)/2;
// cout<<mid<<' '<<check(mid)<<endl;
if(check(mid)) r=mid;
else l=mid+1;
// cout<<l<<' '<<r<<endl;
}
cout<<l<<endl;
}
return 0;
}
```
* T5
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x;scanf("%lld",&x);return x;
}
const ll N=1e6+10;
ll T;
ll a[10];
int main(){
// freopen("E.in","r",stdin);
// freopen("E.out","w",stdout);
T=read();
while(T--){
for(ll i=1;i<=5;i++){
a[i]=read();
}
ll ans=0;
ans+=a[3]/2,a[3]%=2;
ll d=min(a[2],a[4]);
ans+=d,a[2]-=d,a[4]-=d;
d=0;
for(ll i=1;i<=4;i++){
d+=a[i];
}
ll p=min(d,a[5]);
ans+=p;
a[5]-=p;
for(ll i=1;i<=4;i++){
if(a[i]>=p){ a[i]-=p,p=0;break;}
else p-=a[i],a[i]=0;
}
if(a[5]!=0) ans+=a[5]/2,a[1]+=(a[5]%2),a[5]=0;
p=0;
for(ll i=1;i<=3;i++){
p+=a[i];
}
d=min(p/2,a[4]);
ans+=d;
a[4]-=d,d*=2;
for(ll i=1;i<=3;i++){
if(a[i]>=d) {a[i]-=d,d=0;break;}
else d-=a[i],a[i]=0;
}
if(a[4]){
ll lef=0;
for(ll i=1;i<=3;i++){
lef+=a[i];
}
ans+=(lef+a[4])/3;
a[1]=(lef+a[4])%3;
}
d=min(a[3],min(a[2],a[1]));
ans+=d;
a[3]-=d,a[2]-=d,a[1]-=d;
if(a[2] && a[3]){
if(a[2]>=a[3]) p=min(a[3],a[2]/2),ans+=p,a[3]-=p,a[2]-=2*p;
else p=min(a[2],a[3]/2),ans+=p,a[2]-=p,a[3]-=2*p;
}
ans+=(a[1]+2*a[2]+3*a[3])/6;
printf("%d\n",ans);
}
return 0;
}
```
* T6
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <cstdlib>
#define pii pair<int,int>
#define mp make_pair
#define pb emplace_back
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned long long ull;
const int DMAX = 1000000 + 5;
const int INF = 1e9;
const int MOD = 998244353;
using namespace std;
template<class T> inline void read(T &x){
T f=1; x=0; char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9' && ch>='0'){ x=x*10+ch-'0';ch=getchar(); }
x*=f;
}
int n, m, q;
struct edge{
int u, v, w, nxt;
};
edge g[DMAX<<1];
int head[DMAX], cnt=0;
void addedge(int u,int v,int w){
g[++cnt] = edge{u, v, w, head[u]};
head[u] = cnt;
}
struct input{
int u, v, w;
};
input inp[2005];
int get(int lev,int u){
return (lev - 1) * n + u;
}
int dis[DMAX];
bool vst[DMAX];
priority_queue<pii> pq;
void Dij(){
for(int i = 1; i <= get(500, n); i++){
dis[i] = INF, vst[i] = 0;
}
for(int i = 1; i <= 500; i++){
dis[get(i, n)] = 0;
pq.push(mp(0, get(i, n)));
vst[get(i,n)] = 1;
}
while(!pq.empty()){
int u = pq.top().second;
pq.pop();
vst[u] = 0;
for(int i = head[u]; i; i = g[i].nxt){
int v = g[i].v;
if(dis[v] > dis[u] + g[i].w){
dis[v] = dis[u] + g[i].w;
if(!vst[v]) pq.push(mp(-dis[v], v)), vst[v] = 1;
}
}
}
}
int main(){
read(n), read(m);
for(int i = 1; i <= m; i++){
read(inp[i].u), read(inp[i].v), read(inp[i].w);
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= 500; j++){
int gc = __gcd(j, inp[i].w);
int u = get(j, inp[i].u), v = get(gc, inp[i].v);
addedge(v, u, inp[i].w / gc); // reverse addedge v->u
}
for(int j = 1; j <= 500; j++){
int gc = __gcd(j, inp[i].w);
int u = get(j, inp[i].v), v = get(gc, inp[i].u);
addedge(v, u, inp[i].w / gc); // reverse addedge v->u
}
}
Dij();
read(q);
int x;
while(q--){
read(x);
int ans = INF;
for(int i = 1; i <= 500; i++){
ans = min(ans, dis[get(i, x)]);
}
printf("%d\n", ans);
}
return 0;
}
```
# [某大犇](https://www.luogu.com.cn/user/863470)文章----->[Click here](https://www.luogu.com.cn/article/jpacehtk)
# 完结撒花\\(^-^)/