开幕雷击
比赛地址
Rank: 116/1116
Pro: 4/5/10
[A] B-Suffix Array
题意
给出一个仅包含a和b的字符串,对于该字符串的每一个后缀,定义一个键值,键值第i位的值是出现在该后缀中的最后一个和第i位的字母相同的位置与i的差(如果没有就是0).然后对于所有的键值进行排序.求最后结果.
题解
盲猜了一波结论.
定义a[i]为第i位后面第一个相同字母的位置与i的差,然后将这个值看做一个新的字符串,进行后缀排序,排序的结果就是答案.
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 200005;
char str[MAXN];
int n, m;
int st[MAXN], ss[MAXN], en[MAXN], tot, h[MAXN];
int s[MAXN], id[MAXN], height[MAXN], b[MAXN], nxt[MAXN];
bool cmp(const int &i, const int &j) { return s[i]<s[j]; }
void SuffixSort() {
int i, j, k, h;
for (i = 0; i < n; i++) id[i] = i;
std::sort(id, id+n, cmp);
for (i = 0; i < n; i++)
if (i==0||s[id[i]]!=s[id[i-1]]) b[id[i]] = i;
else b[id[i]] = b[id[i-1]];
for (h = 1; h < n; h<<=1) {
for (i = 0; i < n; i++) height[i] = nxt[i] = -1;
for (i = n-1; i >= 0; i--) if (id[i]) {
j = id[i]-h; if (j<0) j+=n;
nxt[j] = height[b[j]]; height[b[j]] = j;
}
j = n-h;
nxt[j] = height[b[j]]; height[b[j]] = j;
for (i = k = 0; i < n; i++) if (height[i] >= 0)
for (j = height[i]; j >= 0; j = nxt[j]) id[k++] = j;
for (i = 0; i < n; i++) if (i > 0 && id[i]+h<n && id[i-1]+h<n &&
b[id[i]]==b[id[i-1]] && b[id[i]+h]==b[id[i-1]+h] )
nxt[id[i]] = nxt[id[i-1]]; else nxt[id[i]] = i;
for (i = 0; i < n; i++) b[i] = nxt[i];
}
}
void clear(int n) {
for (int i = 0; i <= n; i++)
id[i] = height[i] = b[i] = nxt[i] = 0;
}
inline void Write(int x) {
static int sta[9];
register int top=0;
do{
sta[top++]=x%10,x/=10;
}while (x);
while (top) putchar(sta[--top]+48);
putchar(' ');
}
int main() {
while(scanf("%d%s", &n, str) != EOF) {
int upa = 100001, upb = 100001, tot = 0;
for (int i = n; i >= 1; i--) {
if (str[i-1] == 'a') {
if (upa == 100001) st[i] = 1;
else st[i] = 100002 - (upa-i);
upa = i;
} else {
if (upb == 100001) st[i] = 1;
else st[i] = 100002 - (upb-i);
upb = i;
}
ss[i] = st[i];
}
sort(ss+1, ss+n+1);
for (int i = 1; i <= n; i++) if (ss[i] != ss[i-1]) en[++tot] = ss[i];
//for (int i = 1; i <= tot; i++) h[en[i]] = i;
//for (int i = 1; i <= n; i++) a[i] = h[a[i]];
for (int i = 1; i <= n; i++) s[i-1] = lower_bound(en+1, en+1+tot, st[i]) - en;
SuffixSort();
for (int i = 0; i < n; i++) Write(id[i]+1);
printf("\n");
clear(n);
}
return 0;
}
[F] Infinite String Comparision
题意&题解
签到题
代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int main()
{
std::cin.tie(nullptr),std::cout.tie(nullptr),std::ios::sync_with_stdio(false);
string a, b;
string va, vb;
while (cin >> a >> b)
{
va.clear(), vb.clear();
int la = a.length(), lb = b.length();
int ml = la > lb ? la : lb;
ml <<= 1;
ml++;
int t = ceil(ml*1. / la);
while (t--)
for ( char c: a)
va.push_back(c);
t = ceil(ml*1. / lb);
while (t--)
for ( char c: b)
vb.push_back(c);
int ans = strncmp(va.c_str(), vb.c_str(), ml);
if (ans < 0) puts("<");
else if (ans == 0) puts("=");
else puts(">");
}
}
[H] Minimum-cost Flow
题意
给出一个图以及每条边的费用.有一些询问,每一个询问会给出两个数字,u,v.然后对于每一组询问,每条边的流量会变成\frac{u}{v}.求从点1到点n流量为1时的最小费用.
题解
增广路径的选择与流量无关,所以可以先预处理出所有的增广路径,然后对于每一个询问尝试让这些路径流慢就行了.
代码(补)
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 55000
#define M 1100000
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,lsum=1,cnt,q,u,V;
int a[M],b[M],c[M],head[N],from[N],v[N],z[N],d[N];
int cost[N];
LL Ans,flow,F;
struct Flow{
int t,next,re,c,from,fl;
}e[M*8];
IL void Add(int s,int t,int fl,int cost){
e[lsum].t=t; e[lsum].re=lsum+1; e[lsum].fl=fl; e[lsum].c=cost;
e[lsum].from=s; e[lsum].next=head[s]; head[s]=lsum++;
e[lsum].t=s; e[lsum].re=lsum-1; e[lsum].c=-cost;
e[lsum].from=t; e[lsum].next=head[t]; head[t]=lsum++;
}
IL int Min(int a,int b){return (a<b)?a:b;}
IL LL Gcd(LL a,LL b){return (!b)?a:Gcd(b,a%b);}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline int SPFA(){
reg int i=0,t=0,w=1,x=0;
memset(d,INF,sizeof(d[0])*(n+10));
d[1]=0; v[1]=z[w]=1;
while (t!=w){
(t+=1)%cnt; x=z[t]; v[x]=0;
for (i=head[x];i;i=e[i].next)
if (e[i].fl&&d[x]+e[i].c<d[e[i].t]){
d[e[i].t]=d[x]+e[i].c; from[e[i].t]=i;
if (!v[e[i].t]){
(w+=1)%cnt; z[w]=e[i].t; v[e[i].t]=1;
}
}
}
return (d[cnt]==INF)?0:1;
}
inline void Work(){
int i=0,flow=INF;
for (i=from[cnt];i;i=from[e[i].from]) flow=Min(flow,e[i].fl);
cost[++cost[0]]=d[cnt];
for (i=from[cnt];i;i=from[e[i].from]) e[i].fl-=flow,e[e[i].re].fl+=flow;
}
IL void MakeMap(){
reg int i=0;
cnt=n; lsum=1; cost[0]=0;
for (i=1;i<=m;i++){
if (a[i]==b[i]) continue;
Add(a[i],b[i],1,c[i]);
}
while (SPFA()) Work();
}
IL void Find(){
LL p=0,q=V;
Ans=0;
for (i=1;i<=cost[0];i++){
if (p+u<V){
p+=u; Ans+=(LL)u*(LL)cost[i];
} else {
Ans+=(LL)(q-p)*(LL)cost[i]; p=q;
}
}
if (p<q) {puts("NaN"); return;}
p=Gcd(Ans,q);
printf("%lld/%lld\n",Ans/p,q/p);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
while (~scanf("%d%d",&n,&m)){
for (i=1;i<=m;i++){
a[i]=read(); b[i]=read(); c[i]=read();
}
MakeMap(); q=read();
while (q--){
u=read(); V=read();
if (!u) {puts("NaN"); continue;}
Find();
}
memset(head,0,sizeof(head[0])*(n+5));
memset(e,0,sizeof(e[0])*(lsum+10));
}
return 0;
}
[J] Easy Integration
题意
求\int_{0}^{1}(x-x^{2})^{n}dx \mod 998244353
题解
含参变量积分中的Beta函数.
结论:B(p,q)=\frac{\Gamma(p)\Gamma(q)}{\Gamma(p+q)}=\frac{(p-1)!(q-1)!}{(p+q-1)!}
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define MOD 998244353
#define N 2000010
#define INF 0x3f3f3f3f
using namespace std;
int n;
LL x,y;
LL mi[N],inv[N];
inline LL Mi(LL x,LL y){
LL p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
return Res;
}
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Ready(){
LL i=0;
mi[0]=inv[0]=1;
for (i=1;i<=2000005;i++) mi[i]=(mi[i-1]*i)%MOD;
for (i=1;i<=2000005;i++) inv[i]=Mi(mi[i],MOD-2);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
Ready();
while (~scanf("%d",&n)){
x=mi[n];
y=(x*x)%MOD;
y=(y*inv[2*n+1])%MOD;
printf("%lld\n",y);
}
return 0;
}
总结
第一场真的是开幕雷击.
开场做了F和J后陷入了很长一段时间的空档期.A题一直TLE,怀疑是后缀排序的问题,换成上交的板子之后一发AC.之后主要的精力放在了H和I上.写H的时候真的是失了智了,一个变量清空太早导致一直RE,如果能及时发现错误的话,很快就可以想到优化手法了.D题最后推出来了式子,却陷入到了WA的轮回里.
整体状态欠佳,希望明天好好发挥吧.
这次的比赛告诉我们学好高代和淑芬是多么的重要.以后出去打区域赛一定要带上数学笔记去.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020牛客暑期多校第一场
本文地址: 2020牛客暑期多校第一场
