A. Cthulhu
問是否有且僅有一個環，并且環的大小>=3個，要求圖聯通
直接DFS，如果存在一個環，那麼重複通路的節點數目一定是2，首先考慮是鍊，那麼DFS會到鍊的兩個端點，那麼由于這是一個環，兩個端點會被另外一個端點通路，是以次數是2，最後
判斷圖是否聯通即可。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>G[1005];
int vis[105];
int cnt;
void dfs(int x,int fa){
if (vis[x]!=0){
vis[x]++;
// cout<<"--"<<x<<endl;
cnt++;
return;
}else {
vis[x]=1;
}
for (int i=0;i<G[x].size();i++){
if (G[x][i]!=fa)dfs(G[x][i],x);
}
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
for (int i=1;i<=n;i++){
G[i].clear();
}
cnt=0;
int u,v;
memset(vis,0,sizeof(vis));
for (int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,-1);
int flag=0;
for (int i=1;i<=n;i++){
if (vis[i]==0){
flag=1;
}
}
if (flag==0 && cnt==2){
printf("FHTAGN!\n");
}else {
printf("NO\n");
}
}
return 0;
} View Code
B. Increasing by Modulo
給一串序列，每次操作可以給序列中任意多個數+1，并把這些數%M，問最少操作使得序列非遞減。
二分最大操作，那麼每個點的操作一定是小于或等于這個數，貪心的把前面的數盡量置成小的，維護一個前一個的最小狀态，最後判斷最大操作是否可行。進而判斷得到二分上下界，得到最小答案
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxx = 300006;
int a[maxx];
int n,m;
bool judge(int x){
int last=a[1];
if (a[1]+x>=m)last=0;
for (int i=2;i<=n;i++){
int tmp=-1;
if (a[i]>=last){
tmp=a[i];
if (a[i]+x>=m && (a[i]+x)%m>=last){
tmp=last;
}
}else if (a[i]+x>=last){
tmp=last;
}
last=tmp;
if (tmp==-1)return 0;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int l=0,r=m;
int ans;
while(l<=r){
int mid=(l+r)/2;
if (judge(mid)){
ans=mid;
r=mid-1;
}else {
l=mid+1;
}
}
printf("%d\n",ans);
return 0;
} View Code
C. Tavas and Malekas
神仙題。。。給出一個模闆串，以前原串長度，以前在原串中的和模闆串比對的多個首位置，問原串有多少種可能。
肯定是每次枚舉原串首位置，外後更新，判斷即可。但是很顯然直接T飛。。。
首先如果原串兩個相鄰位置a[i]-a[i-1]>=len那麼，a[i-1]不會影響a[i]随便放
如果a[i-1]-a[i-1]<len，那麼我們考慮，模闆串從剩下位置是從a[i]+len-a[i-1]位置和模闆串的第一個位置開始比對。。。如何快速判斷這些位置是否比對呢？？？
考慮Next數組，我們求出NEXT數組後，找失配位置，第一失配位置肯定是Len位置，每次把r指針置為Next[r]，失配位置一定是r位置，打上标記，就能快速判斷是否比對。
最後數出沒有标記的位置，就是可以随便放置的位置
/*
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define LL long long
using namespace std;
const int maxx = 1e6+7,MOD = 1e9+7;
char p[maxx];
int Next[maxx],a[maxx],n,m,vis1[maxx],vis[maxx];
LL qpow(LL a,LL b){
LL sum=1;
while(b){
if(b&1)sum=sum*a%MOD;
a=a*a%MOD;
b/=2;
}
return sum;
}
void get_next(){
memset(vis1,0,sizeof(vis1));
Next[0]=-1;
int k=-1,i=0;
int len=strlen(p);
while(i<len){
if (k==-1 || p[i]==p[k]){
i++;
k++;
Next[i]=k;
}else
k=Next[k];
}
int r=len;
while(r!=-1){
vis1[r]=1;
r=Next[r];
}
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",&p);
for (int i=1;i<=m;i++){
scanf("%d",&a[i]);
}
get_next();
sort(a+1,a+1+m);
int len=strlen(p);
for (int i=1;i<=m;i++){
if (i==1 || a[i]-a[i-1]>=len){
for (int j=a[i];j<=a[i]+len-1;j++){
vis[j]=1;
}
}else if (vis1[a[i-1]+len-a[i]]){
for (int j=a[i-1]+len;j<=a[i]+len-1;j++){
vis[j]=1;
}
}else {
printf("0\n");
return 0;
}
}
LL ans;
int cnt=0;
for (int i=1;i<=n;i++){
if (vis[i]==0){
cnt++;
}
}
ans=qpow((LL)26,cnt);
printf("%lld\n",ans);
return 0;
} View Code
D. Fight Against Traffic
給出N個點，M條路，點i到點j的長度定義為i走個j經過的最小路徑數目，給出起點和終點，在一些沒有直接路徑連接配接的點連接配接一條邊，有多少對這樣增加的路徑，不影響i->j的路徑長度
這題還是非常秀的。。。我們可以用BFS跑出從起點到每個點的距離，每個點到終點的距離，那麼從起點到i的距離+終點到j的距離+1>=起點到終點的距離，起點到j+終點到i的距離+1>=起點到終點的距離，那對答案就是沒有影響的。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxx = 1005;
vector<int>G[maxx];
int n,m;
bool vis[maxx];
int dis_s[maxx];
int dis_t[maxx];
int link[maxx][maxx];
void bfs(int dis[],int s){
queue<int>q;
memset(vis,0,sizeof(vis));
vis[s]=1;
q.push(s);
dis[s]=0;
while(q.size()){
int x=q.front();
q.pop();
for (int i=0;i<G[x].size();i++){
int nx=G[x][i];
if (!vis[nx]){
q.push(nx);
vis[nx]=1;
dis[nx]=dis[x]+1;
}
}
}
}
int main(){
int u,v,s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
link[u][v]=1;
link[v][u]=1;
}
bfs(dis_s,s);
bfs(dis_t,t);
int cnt=0;
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
if (!link[i][j] && dis_s[i]+1+dis_t[j]>=dis_s[t] && dis_t[i]+1+dis_s[j]>=dis_s[t]){
cnt++;
}
}
}
printf("%d\n",cnt);
return 0;
} View Code
E.詢問有多少對i,j滿足a[i]<=y<=a[j]，并且y%x==0中y個數是K的對數
其實就是一個式子a[j]/x-(a[i]-1)/x==k的個數
我們把a[i]排序，這不影響結果（自己腦補）。那麼對于位置i，二分一個上下界滿足這個式子的即可。。。
注意對于i位置的a[i]，左邊界應該是和a[i]相等的數的最小位置（因為有可能相等。。。）
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#define LL long long
using namespace std;
const int maxx = 1e5+6;
int n;
LL x,k;
LL a[maxx];
LL b[maxx];
map<int,int>p1;
int main(){
while(~scanf("%d%lld%lld",&n,&x,&k)){
p1.clear();
for (int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+1+n);
for (int i=1;i<=n;i++){
if (a[i]!=a[i-1]){
p1[a[i]]=i;
}
}
LL ans=0;
for (int i=1;i<=n;i++){
int l=p1[a[i]],r=n;
int low=n+1,up=-1;
while(l<=r){
int mid=(l+r)/2;
if((a[mid]/x-(a[i]-1)/x)==k){
up=max(up,mid);
}
if((a[mid]/x-(a[i]-1)/x)>k){
r=mid-1;
}else {
l=mid+1;
}
}
l=p1[a[i]],r=n;
while(l<=r){
int mid=(l+r)/2;
if((a[mid]/x-(a[i]-1)/x)==k){
low=min(low,mid);
}
if((a[mid]/x-(a[i]-1)/x)>=k){
r=mid-1;
}else {
l=mid+1;
}
}
if (up==-1 || low==n+1){
continue;
}
// cout<<up<<" "<<low<<endl;
ans+=(up-low+1);
}
printf("%lld\n",ans);
}
return 0;
} View Code
F. Minimal string
字元串是坑啊。。。
給A一個字元串，你有兩種操作，一種是把A字元串的最開始的放到字元串B的最後面，
把字元串B的最後面的字元放到字元串C的最後面
要求C的字典序最小，A,B到最後全為空，問C是多少？
寫一個更新數組，從後往前周遊，意義為從i位置往後，最小的字典序的字母。
比較位置i的s[i]和更新數組，如果更新數組更優，把s[i]放到棧裡面去，往後繼續，否則把棧的比更新數組更優的字元放到字元串C中，然後繼續往後找。直到最後
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
stack<char>sta;
char s[100005];
char best[100005];
int main(){
while(~scanf("%s",s)){
int len=strlen(s);
best[len-1]=s[len-1];
for (int i=len-2;i>=0;i--){
best[i]=min(best[i+1],s[i]);
}
string ans;
for (int i=0;i<len;i++){
if (sta.size()==0){
sta.push(s[i]);
}else {
while(sta.size() && sta.top()<=best[i]){
ans+=sta.top();
sta.pop();
}
sta.push(s[i]);
}
}
while(sta.size()){
ans+=sta.top();
sta.pop();
}
cout<<ans<<endl;
}
return 0;
} View Code
就做出A-E，貌似好丢臉。。。