連結：戳這裡
A + B 就不寫了吧
C. Reberland Linguistics time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
First-rate specialists graduate from Berland State Institute of Peace and Friendship. You are one of the most talented students in this university. The education is not easy because you need to have fundamental knowledge in different areas, which sometimes are not related to each other.
For example, you should know linguistics very well. You learn a structure of Reberland language as foreign language. In this language words are constructed according to the following rules. First you need to choose the "root" of the word — some string which has more than 4 letters. Then several strings with the length 2 or 3 symbols are appended to this word. The only restriction — it is not allowed to append the same string twice in a row. All these strings are considered to be suffixes of the word (this time we use word "suffix" to describe a morpheme but not the few last characters of the string as you may used to).
Here is one exercise that you have found in your task list. You are given the word s. Find all distinct strings with the length 2 or 3, which can be suffixes of this word according to the word constructing rules in Reberland language.
Two strings are considered distinct if they have different length or there is a position in which corresponding characters do not match.
Let's look at the example: the word abacabaca is given. This word can be obtained in the following ways:
, where the root of the word is overlined, and suffixes are marked by "corners". Thus, the set of possible suffixes for this word is {aca, ba, ca}.
Input
The only line contains a string s (5 ≤ |s| ≤ 104) consisting of lowercase English letters.
Output
On the first line print integer k — a number of distinct possible suffixes. On the next k lines print suffixes.
Print suffixes in lexicographical (alphabetical) order.
Examples input
abacabaca
output
3
aca
ba
ca
input
abaca
output
Note
The first test was analysed in the problem statement.
In the second example the length of the string equals 5. The length of the root equals 5, so no string can be used as a suffix.
題意：
給出一個字元串,要求從後面開始分别連續的切（2|3）的字串下來,可以一直切到i>5的任意位置就算答案
這裡連續的切長度為（2|3）的字尾字串還有一個要求,就是相鄰的兩個字串假如長度都為2,則這兩個字串不能相等
同理長度為3也一樣
要求輸出能切的字串的個數,并把所有的字串字典序輸出
比賽的時候我看錯了一點條件,隻是連續的兩個長度相等的字串不能一樣,而不是出現過就不能一樣了(mdzz)
思路：
既然必須從後往前連續的分别去切長度為（2|3）的字串,那麼我們把字元串翻轉一下,設定dp狀态
dp[i][0]表示第i個位置取前兩個并且可取 dp[i][0]=1
如何判斷可取 即 dp[i-2][1]=1 || (dp[i-2][0] && (s[i]!=s[i-2] || s[i-1]!=s[i-3]))
dp[i-2][1]=1表示第i-2的位置取了前三個
dp[i-2][0] && (s[i]!=s[i-2] || s[i-1]!=s[i-3]) 表示第i-2個位置取了前兩個
并且目前的字串（s[i]s[i-1]）！=（s[i-2]s[i-3]）
dp[i][1]表示第i個位置取前三個并且可取 dp[i][1]=1
顯然和上面的狀态差不多
具體看代碼
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF (1ll<<60)-1
using namespace std;
int F[10100][2];
vector<string > V;
char s[10010];
int main(){
cin>>s;
int n=strlen(s);
if(n<=5) {
printf("0\n");
return 0;
}
reverse(s,s+n);
if(n-5>=2){string p="";p+=s[1];p+=s[0];V.push_back(p);}
if(n-5>=3){string p="";p+=s[2];p+=s[1];p+=s[0];V.push_back(p);}
F[1][0]=F[2][1]=1;
for(int i=3;i<n-5;i++){
if( F[i-2][1] || (F[i-2][0] && (s[i]!=s[i-2] || s[i-1]!=s[i-3])) ){
string p="";p+=s[i];p+=s[i-1];V.push_back(p);
F[i][0]=1;
}
if(i>=4){
if( F[i-3][0] || (i-5>=0 && F[i-3][1] && (s[i]!=s[i-3] || s[i-1]!=s[i-4] || s[i-2]!=s[i-5])) ){
string p="";p+=s[i];p+=s[i-1];p+=s[i-2];V.push_back(p);
F[i][1]=1;
}
}
}
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
cout<<V.size()<<endl;
for(int i=0;i<V.size();i++)
cout<<V[i]<<endl;
return 0;
}
D. World Tour time limit per test 5 seconds memory limit per test 512 megabytes input standard input output standard output
A famous sculptor Cicasso goes to a world tour!
Well, it is not actually a world-wide. But not everyone should have the opportunity to see works of sculptor, shouldn't he? Otherwise there will be no any exclusivity. So Cicasso will entirely hold the world tour in his native country — Berland.
Cicasso is very devoted to his work and he wants to be distracted as little as possible. Therefore he will visit only four cities. These cities will be different, so no one could think that he has "favourites". Of course, to save money, he will chose the shortest paths between these cities. But as you have probably guessed, Cicasso is a weird person. Although he doesn't like to organize exhibitions, he likes to travel around the country and enjoy its scenery. So he wants the total distance which he will travel to be as large as possible. However, the sculptor is bad in planning, so he asks you for help.
There are n cities and m one-way roads in Berland. You have to choose four different cities, which Cicasso will visit and also determine the order in which he will visit them. So that the total distance he will travel, if he visits cities in your order, starting from the first city in your list, and ending in the last, choosing each time the shortest route between a pair of cities — will be the largest.
Note that intermediate routes may pass through the cities, which are assigned to the tour, as well as pass twice through the same city. For example, the tour can look like that:
. Four cities in the order of visiting marked as overlines:[1, 5, 2, 4].
Note that Berland is a high-tech country. So using nanotechnologies all roads were altered so that they have the same length. For the same reason moving using regular cars is not very popular in the country, and it can happen that there are such pairs of cities, one of which generally can not be reached by car from the other one. However, Cicasso is very conservative and cannot travel without the car. Choose cities so that the sculptor can make the tour using only the automobile. It is guaranteed that it is always possible to do.
Input
In the first line there is a pair of integers n and m (4 ≤ n ≤ 3000, 3 ≤ m ≤ 5000) — a number of cities and one-way roads in Berland.
Each of the next m lines contains a pair of integers ui, vi (1 ≤ ui, vi ≤ n) — a one-way road from the city ui to the city vi. Note that uiand vi are not required to be distinct. Moreover, it can be several one-way roads between the same pair of cities.
Output
Print four integers — numbers of cities which Cicasso will visit according to optimal choice of the route. Numbers of cities should be printed in the order that Cicasso will visit them. If there are multiple solutions, print any of them.
Example input
8 9
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 8
8 5
output
2 1 8 7
Note
Let d(x, y) be the shortest distance between cities x and y. Then in the example d(2, 1) = 3, d(1, 8) = 7, d(8, 7) = 3.
The total distance equals 13.
題意：
給出n個點m條邊的有向圖, 每條邊的長度為1
要求找出四個點a,b,c,d使得 a->b + b->c + c->d 的距離最大 其中a->b ,b->c ,c->d代表兩點之間的最短路徑
(1<=n<=3000) (1<=m<=5000)
思路：
1：先用複雜度内的最短路算法求出所有的i->j的最短路
2：我們可以先枚舉所有的b->c 然後再去枚舉a和d。顯然對答案的貢獻我們要求最大,是以a->b 和 c->的要盡可能的大
是以我們可以直接求出最大的a->b 和 c->d 但是因為a,b,c,d不能重點 ,我們直接枚舉前三大的就可以了
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF 1e8
using namespace std;
int n,m,tot;
struct edge{
int v,w,next;
}e[5050];
int head[3010],vis[3010];
int mp[3030][3030],dis[3030];
vector< pair<int ,int> > V1[5050];
vector< pair<int ,int> > V2[5050];
void init(){
mst(head,-1);
tot=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) mp[i][j]=0;
else mp[i][j]=INF;
}
}
}
void Add(int u,int v){
e[tot].v=v;
e[tot].w=1;
e[tot].next=head[u];
head[u]=tot++;
}
void SPFA(int x){
mst(vis,0);
for(int i=1;i<=n;i++) dis[i]=INF;
dis[x]=0;
vis[x]=1;
queue<int> qu;
qu.push(x);
while(!qu.empty()){
int u=qu.front();
qu.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v]){
vis[v]=1;
qu.push(v);
}
}
}
}
for(int i=1;i<=n;i++)
mp[x][i]=min(mp[x][i],dis[i]);
}
void solve(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
if(mp[i][j]!=INF) V1[i].push_back(make_pair(mp[i][j],j));
if(mp[j][i]!=INF) V2[i].push_back(make_pair(mp[j][i],j));
}
}
for(int i=1;i<=n;i++){
sort(V1[i].begin(),V1[i].end());
reverse(V1[i].begin(),V1[i].end());
sort(V2[i].begin(),V2[i].end());
reverse(V2[i].begin(),V2[i].end());
}
int t1,t2,t3,t4,ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j || mp[i][j]==INF) continue;
for(int k=0;k<3 && k<V1[j].size();k++){
if(i==V1[j][k].second) continue;
if(j==V1[j][k].second) continue;
for(int l=0;l<3 && l<V2[i].size();l++){
if(i==V2[i][l].second) continue;
if(j==V2[i][l].second) continue;
if(V1[j][k].second==V2[i][l].second) continue;
int tmp=V2[i][l].first + mp[i][j] + V1[j][k].first;
if(tmp > ans){
ans=tmp;
t1=V2[i][l].second;
t2=i;
t3=j;
t4=V1[j][k].second;
}
}
}
}
}
cout<<t1<<" "<<t2<<" "<<t3<<" "<<t4<<endl;
///cout<<ans<<endl;
}
int main(){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
Add(u,v);
}
for(int i=1;i<=n;i++) SPFA(i);
/*for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d ",mp[i][j]);
}
cout<<endl;
}*/
solve();
return 0;
}