2019.6.26 JZ DAY2总结
Description
给出p个长度不超过10的字符串，字符集大小为n。
如果这p个串都不是字符串s的子串，则认为s是幸运的。
求长度为m的幸运串个数
Input
第一行三个正整数n,m,p。
第二行n个不同的字符，表示字符集，其ASCII码大于32。
接下来p行每行一个字符串，表示不允许被包含的串。
Output
一行一个整数，表示幸运串个数。
Sample Input
2 3 1
ab
bb
Sample Output
5
Hint
【样例说明】
aaa aab aba baa bab 共5个串为幸运串。
【数据规模】
对于20%的数据，m ≤ 6，n ≤ 10；
对于50%的数据，p个串的长度不超过4，m ≤ 50，n ≤ 10；
对于100%的数据，n ≤ 50，m ≤ 50，p ≤ 10。
考场没有一点思路，直接弃疗。
考后知道正解是AC自动机+DP，说明并没有完全了解AC自动机的原理及运用。考后巩固AC自动机，可是感觉理解程度好像还没有初学那次那么深刻，花了大量的时间后算是比较理解AC自动机了。对于我的弱项DP，不过本题的DP转移还是比较良心的非常易懂。And这题不给取模，只能用大数加法，我发现我不会大数加法，只能暂时copy，赶在今明两天学会。
大概思路将所有的病毒串建一个AC自动机，然后在AC自动机上做DP。设表示取到第i个字母在AC自动机上的位置为j时的方案数，转移显然$f[i + 1][tmp] += f[i][j] $ tmp为枚举在j位置时加上一个枚举的字母k的位置。注意AC自动机的fail数组要下传即可。
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 55;
struct Edge{
int vis[maxn * 10],id,fail,p;
} f[maxn * 11];
int n,m,p,asc[maxn * 10],cnt;
queue <int> q;
struct largeint
{
ll num[110],len;
largeint()
{
memset(num,0,sizeof(num)),len=1;
}
largeint operator=(const char s[])
{
len=strlen(s);
for(int i = 0; i <= len -1; i ++) num[i] = s[len - i - 1] - '0';
while (num[len-1]==0 && len>1) -- len;
return *this;
}
largeint operator=(const ll x)
{
ll temp=x;
len=1;
do
{
num[len-1]=temp%10;
temp/=10,len++;
}
while (temp);
while (num[len-1]==0 && len>1)--len;
return *this;
}
largeint operator+(const largeint &x)const
{
largeint temp;
temp.len=max(len,x.len)+1;
for (int i =0; i <= temp.len - 1; i ++)
{
temp.num[i] += num[i] + x.num[i];
temp.num[i+1] = temp.num[i] / 10;
temp.num[i] %= 10;
}
while (temp.num[temp.len-1]==0 && temp.len>1)--temp.len;
return temp;
}
void prin()
{
for (int i = len - 1; i >= 0; i --) printf("%lld",num[i]);
printf("\n");
}
} v[maxn][maxn * 11];
void insert(string s)
{
int root = 0;
for (int i = 0; s[i]; i ++)
{
int id = asc[s[i]];
if (!f[root].vis[id]) f[root].vis[id] = ++ cnt,root = cnt; else root = f[root].vis[id];
}
f[root].p = 1;
}
void Get_fail()
{
for (int i = 1; i <= n; i ++) if (f[0].vis[i]) q.push(f[0].vis[i]),f[f[0].vis[i]].fail = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
if (f[f[u].fail].p) f[u].p = 1;
for (int i = 1; i <= n; i ++)
{
if (f[u].vis[i]) f[f[u].vis[i]].fail = f[f[u].fail].vis[i],q.push(f[u].vis[i]); else f[u].vis[i] = f[f[u].fail].vis[i];
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
scanf("\n");
for (int i = 1; i <= n; i ++) asc[getchar()] = i;
for (int i = 1; i <= p; i ++)
{
string s;
cin >> s;
insert(s);
}
Get_fail();
v[0][0] = 1;
for (int i = 0; i <= m - 1; i ++)
for (int j = 0; j <= cnt; j ++)
for (int k = 1,tmp; k <= n; k ++)
{
if (f[j].vis[k] != -1)
{
tmp = f[j].vis[k];
if (!f[tmp].p) v[i + 1][tmp] = v[i + 1][tmp] + v[i][j];
} else
{
tmp = f[j].fail;
while (tmp) {if (f[tmp].vis[k] != -1) break;tmp = f[tmp].fail;};
if (tmp == -1) tmp = 0; else tmp = f[tmp].vis[k];
if (!f[tmp].p) v[i + 1][tmp] = v[i + 1][tmp] + v[i][j];
}
}
largeint ans;
for (int i = 0; i <= cnt; i ++) ans = ans + v[m][i];
ans.prin();
return 0;
}
Description
XX星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure—超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时XX星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。
Input
输入包括多个测试实例，每个实例包括：
第一行有2个正整数n 和m ,表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速speedSARS。
接下来一行有2个正整数Start,End, 表示寻路的起终点。
Output
打印一行，仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达，那么输出-1。
Sample Input
4 4
1 2 2
2 3 4
1 4 1
3 4 2
1 3
Sample Output
1
Hint
【样例说明】
路径为1->4->3。
【数据规模】
对于30%的数据，输入数据是一棵树。
对于60%的数据，m ≤ 1000；
对于100%的数据，n ≤ 100，m ≤ n * (n + 1) / 2，边权 ≤ 1e9。
唉考场上遇到这样的题竟然没有切掉着实可惜，我甚至还记得在某谷上面做过原题。关键是考场的时候思路错误，然后还一直按这个思路深究没有考虑其他方法所以错了，考场用二分加spfa，我知道自己的正确性时错误的，自己都可以出数据hack掉，可竟然骗了54.5pts。正解最小生成树加并查集，水到不行。先将所有边按照边权从小到大拍，然后n2暴力即可。时间复杂度貌似过不了可是还是过了。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 110;
const int maxm = 5100;
struct Edge{
int from,to,val;
} f[maxm << 1];
int n,m,s,t,cnt,fa[maxn],ans;
bool cmp(Edge a,Edge b) {return a.val < b.val;}
void pre()
{
for (int i = 1; i <= n; i ++) fa[i] = i;
}
int get(int a)
{
if (a == fa[a]) return a; else return fa[a] = get(fa[a]);
}
void solve()
{
ans = 1e9 + 10;
for (int i = 1; i <= cnt; i ++)
{
pre();
for (int j = i,x,y; j <= cnt; j ++)
{
x = get(f[j].from),y = get(f[j].to);
if (x != y) fa[x] = y;
if (get(s) == get(t))
{
if (f[j].val - f[i].val < ans) ans = f[j].val - f[i].val;
break;
}
}
}
}
int main()
{
while (scanf("%d%d",&n,&m) != EOF)
{
cnt = 0;
for (int i = 1,u,v,w; i <= m; i ++)
{
scanf("%d%d%d",&u,&v,&w);
f[++ cnt].from = u,f[cnt].to = v,f[cnt].val = w;
f[++ cnt].from = v,f[cnt].to = u,f[cnt].val = w;
}
scanf("%d%d",&s,&t);
sort(f + 1,f + 1 + cnt,cmp);
solve();
if (ans == 1e9 + 10) printf("%d",-1); else printf("%d",ans);
}
return 0;
}
Description
给出n个数a[i]，要求你支持共m次操作，种类如下：
1.I x y : 在第x个数前插入一个数y；
2.D x : 删除第x个数；
3.R x y : 把第x个数改成y；
4.Q x y : 输出max{a[i] + a[i + 1] + … + a[j] | x<=i<=j<=y}。
Input
第一行一个整数n。
第二行n个整数表示a[i]。
第三行一个整数m。
接下来m行每行一个操作，格式见上。
Output
对于每个操作Q输出一行一个整数，表示相应答案。
Sample Input
5
3 -4 3 -1 6
10
I 6 2
Q 3 5
R 5 -4
Q 3 5
D 2
Q 1 5
I 2 -10
Q 1 6
R 2 -1
Q 1 6
Sample Output
8
3
6
3
5
Hint
【数据规模】
对于40%的数据，n,m ≤ 1000；
对于100%的数据， n,m ≤ 10W，A中元素 ≤ 1W，数列保证非空。
考场看到这种题就知道是一个我不会的数据结构题，直接上暴力。结果拿了45.5pts，这数据出的也真的是良心。
正解是平衡树，用splay和无权treap均可，可我两个都不会，还得学，暂时先上暴力code。
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e3 + 10;
int n,m,a[maxn],ans,now;
int max(int a,int b) {return a > b ? a : b;}
int main()
{
scanf("%d",&n);
for (int i = 1; i <= n; i ++) scanf("%d",&a[i]);
scanf("%d",&m);
for (int i = 1; i <= m; i ++)
{
char c;
int x,y;
cin >> c;
if (c == 'I')
{
cin >> x >> y;
n ++;
for (int i = n; i >= x + 1; i --) a[i] = a[i - 1];
a[x] = y;
}
if (c == 'D')
{
cin >> x;
n --;
for (int i = x; i <= n; i ++) a[i] = a[i + 1];
}
if (c == 'R')
{
cin >> x >> y;
a[x] = y;
}
if (c == 'Q')
{
cin >> x >> y;
ans = -0x3f3f3f3f;
for (int i = x; i <= y; i ++) ans = max(ans,a[i]);
now = 0;
for (int i = x; i <= y; i ++)
{
now += a[i];
if (now < 0) now = 0; else ans = max(ans,now);
}
printf("%d\n",ans);
}
}
return 0;
}
昨天第一题的AC自动机复习了好久，所以没来得及打总结，晚一天补上。
昨日分数0+54.5+45.5=100，有进步，rank13，继续加油鸭。