Blank
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
There are N blanks arranged in a row. The blanks are numbered 1,2,…,N from left to right.
Tom is filling each blank with one number in {0,1,2,3}. According to his thought, the following M conditions must all be satisfied. The ith condition is:
There are exactly xi different numbers among blanks ∈[li,ri].
In how many ways can the blanks be filled to satisfy all the conditions? Find the answer modulo 998244353.
InputThe first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.
In each test case, there are two integers n(1≤n≤100) and m(0≤m≤100) in the first line, denoting the number of blanks and the number of conditions.
For the following m lines, each line contains three integers l,r and x, denoting a condition(1≤l≤r≤n, 1≤x≤4).
OutputFor each testcase, output a single line containing an integer, denoting the number of ways to paint the blanks satisfying all the conditions modulo 998244353.
Sample Input
2 1 0 4 1 1 3 3
Sample Output
4 96
定义 dp[i][j][k][t] 代表填完前 t 个位置后，{0, 1, 2, 3} 这 4 个数字最后一次出现的位置，排序后为 i, j, k, t(i < j < k < t) 的方案数目，则按照第 t + 1 位的数字的四种选择，可以得到四种转移。
对于限制可以按照限制区间的右端点分类，求出 dp[i][j][k][t] 后，找到所有以 t 为区间右端点的限制条件，如果当前状态不满足所有限制条件则不合法，不再向后转移。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e2+10;
const int mod=998244353;
int n,m,p,dp[2][maxn][maxn][maxn];
vector<pair<int,int> > v[maxn];
void add(int &x){if(x>=mod) x-=mod;}
void solve(){
scanf("%d%d",&n,&m);
rep(i,1,n) v[i].clear();
rep(i,1,m){
int l,r,x;scanf("%d%d%d",&l,&r,&x);
v[r].pb({l,x});
}
dp[0][0][0][0]=1;
for(int i=1,p=1;i<=n;i++,p^=1){
rep(j,0,i) rep(k,0,j) rep(t,0,k)
dp[p][j][k][t]=0;
rep(j,0,i-1) rep(k,0,j) rep(t,0,k){
add(dp[p][j][k][t]+=dp[p^1][j][k][t]);
add(dp[p][i-1][k][t]+=dp[p^1][j][k][t]);
add(dp[p][i-1][j][t]+=dp[p^1][j][k][t]);
add(dp[p][i-1][j][k]+=dp[p^1][j][k][t]);
}
rep(j,0,i-1) rep(k,0,j) rep(t,0,k){
for(auto u:v[i]) if(1+(j>=u.first)+(k>=u.first)+(t>=u.first)!=u.second)
dp[p][j][k][t]=0;
}
}
int ans=0;
for(int i=0,p=n&1;i<n;i++){
rep(j,0,i) rep(k,0,j) add(ans+=dp[p][i][j][k]);
}
printf("%d\n", ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Vacation
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Tom and Jerry are going on a vacation. They are now driving on a one-way road and several cars are in front of them. To be more specific, there are n cars in front of them. The ith car has a length of li, the head of it is si from the stop-line, and its maximum velocity is vi. The car Tom and Jerry are driving is l0 in length, and s0 from the stop-line, with a maximum velocity of v0.
The traffic light has a very long cycle. You can assume that it is always green light. However, since the road is too narrow, no car can get ahead of other cars. Even if your speed can be greater than the car in front of you, you still can only drive at the same speed as the anterior car. But when not affected by the car ahead, the driver will drive at the maximum speed. You can assume that every driver here is very good at driving, so that the distance of adjacent cars can be kept to be 0.
Though Tom and Jerry know that they can pass the stop-line during green light, they still want to know the minimum time they need to pass the stop-line. We say a car passes the stop-line once the head of the car passes it.
Please notice that even after a car passes the stop-line, it still runs on the road, and cannot be overtaken.
InputThis problem contains multiple test cases.
For each test case, the first line contains an integer n (1≤n≤105,∑n≤2×106), the number of cars.
The next three lines each contains n+1 integers, li,si,vi (1≤si,vi,li≤109). It's guaranteed that si≥si+1+li+1,∀i∈[0,n−1]
OutputFor each test case, output one line containing the answer. Your answer will be accepted if its absolute or relative error does not exceed 10−6.
Formally, let your answer be a, and the jury's answer is b. Your answer is considered correct if |a−b|max(1,|b|)≤10−6.
The answer is guaranteed to exist.
Sample Input
1 2 2 7 1 2 1 2 1 2 2 10 7 1 6 2 1
Sample Output
3.5000000000 5.0000000000
签到题，考虑最终通过停止线的时候，一定是一个车后面堵着剩余所有的车，那么影响时间的就只有最前面这辆车，所以对于每一辆车，假设是它是和 0 车堵在一起的最靠前的一辆车，那么可以计算出一个值，所有的车的计算值的最大值就是答案。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
struct node{
int l,s,v;
};
node a[maxn];
ll pre[maxn];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
node st;
rep(i,0,n) pre[i]=0;
scanf("%d",&st.l);
rep(i,1,n) scanf("%d",&a[i].l);
scanf("%d",&st.s);
rep(i,1,n) scanf("%d",&a[i].s);
scanf("%d",&st.v);
rep(i,1,n) scanf("%d",&a[i].v);
rep(i,1,n) pre[i]=pre[i-1]+1ll*a[i].l;
double t=0;
dep(i,n,1){
double tmp=(double)(pre[i]+1ll*a[i].s)/(double)(1.0*a[i].v);
t=max(t,tmp);
}
t=max(t,(double)st.s/(double)(1.0*st.v));
printf("%.10lf\n",t);
}
return 0;
}
Path
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.
Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl's home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.
Note, if Jerry can't reach his girl's house in the very beginning, the answer is obviously zero. And you don't need to guarantee that there still exists a way from Jerry's house to his girl's after blocking some edges.
InputThe input begins with a line containing one integer T(1≤T≤10), the number of test cases.
Each test case starts with a line containing two numbers n,m(1≤n,m≤10000), the number of houses and the number of one-way roads in the neighbourhood.
m lines follow, each of which consists of three integers x,y,c(1≤x,y≤n,1≤c≤109), denoting that there exists a one-way road from the house indexed x to y of length c.
OutputPrint T lines, each line containing a integer, the answer.
Sample Input
1 3 4 1 2 1 2 3 1 1 3 2 1 3 3
Sample Output
3
签到题，先求出最短路，然后保留所有满足 dey− dex= ew 的边，对于新的图求 1 到 n 的最小割即为答案。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn=(int)1e4+100;
const ll INF=(ll)1e18;
struct Edge{
int u,v;
ll w;
int next;
}g[maxn<<1];
int head[maxn],cnt,n,m;
bool vis[maxn];
ll dis[maxn];
void addedge(int u,int v,ll w) {
g[cnt].u=u;
g[cnt].v=v;
g[cnt].w=w;
g[cnt].next=head[u];
head[u]=cnt++;
}
struct node{
int to;
ll cap;
unsigned rev;
};
int dep[maxn];
vector<node> v[maxn];
void add_Node(int from, int to, ll cap){
v[from].push_back((node) { to, cap, static_cast<unsigned int>(v[to].size()) });
v[to].push_back((node) { from, 0, static_cast<unsigned int>(v[from].size() - 1) });
}
int bfs(int s,int t){
queue<int> q;
while(!q.empty()) q.pop();
memset(dep,-1,sizeof(dep));
dep[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<v[u].size();i++)
if(v[u][i].cap>0&&dep[v[u][i].to]==-1){
dep[v[u][i].to]=dep[u]+1;
q.push(v[u][i].to);
}
}
return dep[t]!=-1;
}
ll dfs(int u,int t,ll micap){
if(u==t) return micap;
ll tmp;
for(int i=0;i<v[u].size();i++){
node &now=v[u][i];
if(now.cap>0&&dep[u]+1==dep[now.to]&&(tmp=dfs(now.to,t,min(1ll*now.cap,micap)))){
now.cap-=tmp;
v[now.to][now.rev].cap+=tmp;
return tmp;
}
}
return 0;
}
ll dinic(int s,int t){
ll ans=0,tmp;
while(bfs(s,t))
while(1){
tmp=dfs(s,t,INF);
if(tmp==0)break;
ans+=tmp;
}
return ans;
}
void dijkstra(int s) {
priority_queue<pii,vector<pii>,greater<pii> > Q;
rep(i,1,n) dis[i]=INF;
dis[s]=0;
memset(vis,false,sizeof(vis));
Q.push(make_pair(dis[s],s));
while(!Q.empty()) {
pii tmp = Q.top();
Q.pop();
int x = tmp.second;
if(vis[x]) continue;
vis[x] = true;
for(int i = head[x]; i; i = g[i].next) {
if(dis[g[i].v] > dis[x] + g[i].w) {
dis[g[i].v] = dis[x] + g[i].w;
Q.push(make_pair(dis[g[i].v], g[i].v));
}
}
}
rep(i,1,cnt-1) if(abs(dis[g[i].u]-dis[g[i].v])==g[i].w){
add_Node(g[i].u,g[i].v,g[i].w);
}
return;
}
void init(){
rep(i,0,n) head[i]=0,v[i].clear();
cnt=1;
}
void solve(){
scanf("%d%d",&n,&m);
init();
rep(i,1,m){
int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);
addedge(u,v,w);
}
if(n==1){printf("0\n");return;}
dijkstra(1);
printf("%lld\n",dinic(1,n));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Typewriter
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
One day, Jerry found a strange typewriter. This typewriter has 2 input modes: pay p coins to append an arbitrary single letter to the back, or q coins to copy a substring that has already been outputted and paste it in the back.
Jerry now wants to write a letter to Tom. The letter is a string S which contains only lowercase Latin letters. But as Jerry is not very wealthy, he wants to know the minimum number of coins he needs to write this letter.
InputThis problem contains multiple test cases. Process until the end of file.
For each test case, the first line contains string S (|S|≤2×105,∑|S|≤5×106), consisting of only lowercase Latin letters. And the second line contains 2 integers pand q (1≤p,q<231).
OutputFor each test case, output one line containing the minimum number of coins Jerry needs to pay.
Sample Input
abc 1 2 aabaab 2 1
Sample Output
3 6
后缀自动机模版题，dp方程容易想到，但是难点在于如何判断前缀中包含这个后缀，这里需要用到SAM；
容易想到对于 i 从小到大处理，维护使得 s[j : i] ∈ s[1 : j − 1] 的最小的 j(s[l : r] 表示子串slsl+1…sr)，那么记 dp[i] 为输出前 i 个字符的最小代价，则 dp[i] = min{dp[i−1]+p, dp[j−1]+q}。用 SAM 维护 s[1 : j − 1]，若 s[1 : j − 1] 中包含 s[j : i + 1]，即加入第 i + 1 个字符仍然能复制，就不需要做任何处理。否则，重复地将第 j 个字符加入后缀自动机并 j = j + 1，相应维护 s[j : i + 1] 在后缀自动机上新的匹配位置，直到 s[j, i + 1] ∈ s[1, j − 1]。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)4e5+100;
struct SAM{
int next[maxn][26],pre[maxn],len[maxn];
int root,tot,last;
int newnode(int l){
pre[tot]=-1;
for(int i=0;i<26;++i) next[tot][i]=-1;
len[tot++]=l; return tot-1;
}
void init(){
tot=0;
last=root=newnode(0);
}
void insert(int x){
int p=last; int cur=newnode(len[p]+1);
while(p!=-1&&next[p][x]==-1){
next[p][x]=cur; p=pre[p];
}
if(p==-1) pre[cur]=root;
else{
int q=next[p][x];
if(len[q]==len[p]+1) pre[cur]=q;
else{
int tmp = newnode(len[p]+1);
for(int i=0;i<26;++i) next[tmp][i]=next[q][i];
pre[tmp]=pre[q]; pre[q]=pre[cur]=tmp;
while(p!=-1&&next[p][x]==q){
next[p][x]=tmp; p=pre[p];
}
}
}
last=cur;
}
}sam;
char s[maxn];
ll dp[maxn],p,q;
int n,m;
int main(){
while(scanf("%s",s+1)!=EOF){
n=strlen(s+1); scanf("%lld %lld",&p,&q);
for(int i=0;i<=n;++i) dp[i]=i*p; sam.init();
for(int i=1,j=0,cur=sam.root;i<=n;++i){
if(j) j--;
while(sam.pre[cur]!=-1&&sam.len[sam.pre[cur]]>=j) cur=sam.pre[cur];
dp[i]=min(dp[i-1]+p,dp[i]);
while(i+j<=n&&sam.next[cur][s[i+j]-'a']!=-1){
cur=sam.next[cur][s[i+j]-'a']; j++;
dp[i-1+j]=min(dp[i-1+j],dp[i-1]+q);
}
sam.insert(s[i]-'a');
}
printf("%lld\n",dp[n]);
}
}
String
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Tom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is k and lexicographical order is the smallest. It's simple and he solved it with ease.
But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom trouble any more.
The constraints are: the number of occurrences of the ith letter from a to z (indexed from 1 to 26) must in [Li,Ri].
Tom gets dizzy, so he asks you for help.
InputThe input contains multiple test cases. Process until the end of file.
Each test case starts with a single line containing a string S(|S|≤105)and an integer k(1≤k≤|S|).
Then 26 lines follow, each line two numbers Li,Ri(0≤Li≤Ri≤|S|).
It's guaranteed that S consists of only lowercase letters, and ∑|S|≤3×105.
OutputOutput the answer string.
If it doesn't exist, output −1.
Sample Input
aaabbb 3 0 3 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output
abb
贪心，一位位地构造答案字符串，每次贪心地加能加入的最小的字符 (判断能否加入只要判断加入之后原字符串剩下的后缀中的每种字符的数目能否足够满足条件)。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
int n,k,l[27],r[27],has[27],cnt[maxn][27];
char str[maxn],ans[maxn];
vector<int> g[27];
void solve(){
n=strlen(str+1);
rep(i,0,26) cnt[n+1][i]=0,has[i]=0,g[i].clear();
rep(i,1,26) scanf("%d%d",&l[i],&r[i]);
dep(i,n,1) rep(j,1,26) cnt[i][j]=cnt[i+1][j]+(str[i]=='a'+j-1);
rep(i,1,n) g[str[i]-'a'+1].pb(i);
vector<int>::iterator head[27];
rep(i,1,26) head[i]=g[i].begin();
int last=-1;
rep(i,1,k){
bool flag1=0;
rep(j,1,26){
if(has[j]==r[j]) continue;
while(head[j]!=g[j].end()&&(*head[j])<=last) head[j]++;
if(head[j]==g[j].end()) continue;
has[j]++;
bool flag2=1;
int pos=(*head[j]),sum=0;
rep(t,1,26){
if(cnt[pos+1][t]+has[t]<l[t]) flag2=0;
sum+=max(l[t]-has[t],0);
}
if(sum>k-i) flag2=0;
sum=0;
rep(t,1,26) sum+=min(cnt[pos+1][t],r[t]-has[t]);
if(sum<k-i) flag2=0;
if(!flag2) has[j]--;
else{
ans[i]='a'+j-1;
flag1=1;
last=pos;
break;
}
}
if(!flag1){printf("-1\n");return;}
}
rep(i,1,k) printf("%c",ans[i]);
printf("\n");
}
int main(){
while(~scanf("%s%d",str+1,&k)) solve();
}
