It's one more school day now. Sasha doesn't like classes and is always bored at them. So, each day he invents some game and plays in it alone or with friends.
Today he invented one simple game to play with Lena, with whom he shares a desk. The rules are simple. Sasha draws n sticks in a row. After that the players take turns crossing out exactly k sticks from left or right in each turn. Sasha moves first, because he is the inventor of the game. If there are less than k sticks on the paper before some turn, the game ends. Sasha wins if he makes strictly more moves than Lena. Sasha wants to know the result of the game before playing, you are to help him.
The first line contains two integers n and k (1 ≤ n, k ≤ 1018, k ≤ n) — the number of sticks drawn by Sasha and the number k — the number of sticks to be crossed out on each turn.
If Sasha wins, print "YES" (without quotes), otherwise print "NO" (without quotes).
You can print each letter in arbitrary case (upper of lower).
1 1
YES
10 4
NO
In the first example Sasha crosses out 1 stick, and then there are no sticks. So Lena can't make a move, and Sasha wins.
In the second example Sasha crosses out 4 sticks, then Lena crosses out 4 sticks, and after that there are only 2 sticks left. Sasha can't make a move. The players make equal number of moves, so Sasha doesn't win.
A题就直接看下答案是不是2的倍数，没仔细看题，卡LL，就是看下可以进行几轮呗，不被整除多进行两轮
#include<bits/stdc++.h> using namespace std; int main() { long long n,k; cin>>n>>k; int f=n/k; printf("%s",f&1?"YES":"NO"); return 0; }
It's hard times now. Today Petya needs to score 100 points on Informatics exam. The tasks seem easy to Petya, but he thinks he lacks time to finish them all, so he asks you to help with one..
There is a glob pattern in the statements (a string consisting of lowercase English letters, characters "?" and "*"). It is known that character "*" occurs no more than once in the pattern.
Also, n query strings are given, it is required to determine for each of them if the pattern matches it or not.
Everything seemed easy to Petya, but then he discovered that the special pattern characters differ from their usual meaning.
A pattern matches a string if it is possible to replace each character "?" with one good lowercase English letter, and the character "*" (if there is one) with any, including empty, string of bad lowercase English letters, so that the resulting string is the same as the given string.
The good letters are given to Petya. All the others are bad.
The first line contains a string with length from 1 to 26 consisting of distinct lowercase English letters. These letters are good letters, all the others are bad.
The second line contains the pattern — a string s of lowercase English letters, characters "?" and "*" (1 ≤ |s| ≤ 105). It is guaranteed that character "*" occurs in s no more than once.
The third line contains integer n (1 ≤ n ≤ 105) — the number of query strings.
n lines follow, each of them contains single non-empty string consisting of lowercase English letters — a query string.
It is guaranteed that the total length of all query strings is not greater than 105.
Print n lines: in the i-th of them print "YES" if the pattern matches the i-th query string, and "NO" otherwise.
You can choose the case (lower or upper) for each letter arbitrary.
ab
a?a
2
aaa
aab
YES
NO
abc
a?a?a*
4
abacaba
abaca
apapa
aaaaax
NO
YES
NO
YES
In the first example we can replace "?" with good letters "a" and "b", so we can see that the answer for the first query is "YES", and the answer for the second query is "NO", because we can't match the third letter.
Explanation of the second example.
- The first query: "NO", because character "*" can be replaced with a string of bad letters only, but the only way to match the query string is to replace it with the string "ba", in which both letters are good.
- The second query: "YES", because characters "?" can be replaced with corresponding good letters, and character "*" can be replaced with empty string, and the strings will coincide.
- The third query: "NO", because characters "?" can't be replaced with bad letters.
- The fourth query: "YES", because characters "?" can be replaced with good letters "a", and character "*" can be replaced with a string of bad letters "x".
给个字符串，？替代一个字符，但是这个字符必须在给定序列内，还有*，可以替代一个字符串或者空串。我选择stl模拟
#include<bits/stdc++.h> using namespace std; int main() { string s; cin>>s; set<int>S; for(int i=0; s[i]; i++) S.insert(s[i]); cin>>s; int l1=s.length(); int fa=-1; for(int i=0; s[i]; i++) if(s[i]=='*') { fa=i; s.erase(s.begin()+i); l1-=1; break; } int n; cin>>n; while(n--) { string c1; cin>>c1; int f=0; int l2=c1.length(); l2-=l1; if(l2<0||l2>0&&fa==-1) f=1; else { if(fa!=-1) { for(int j=fa; j<fa+l2; j++) if(S.count(c1[j])) { f=1; break; } c1.erase(fa,l2); } if(f==0) { for(int i=0; s[i]; i++) { if(s[i]=='?') { if(S.count(c1[i])==0) f=1; } else if(s[i]!=c1[i])f=1; if(f)break; } } } printf("%s ",f==0?"YES":"NO"); } }
我感觉六哥的dfs也不错，因为我用了stl，所以有点慢的
Misha and Grisha are funny boys, so they like to use new underground. The underground has n stations connected with n - 1 routes so that each route connects two stations, and it is possible to reach every station from any other.
The boys decided to have fun and came up with a plan. Namely, in some day in the morning Misha will ride the underground from station sto station f by the shortest path, and will draw with aerosol an ugly text "Misha was here" on every station he will pass through (including sand f). After that on the same day at evening Grisha will ride from station t to station f by the shortest path and will count stations with Misha's text. After that at night the underground workers will wash the texts out, because the underground should be clean.
The boys have already chosen three stations a, b and c for each of several following days, one of them should be station s on that day, another should be station f, and the remaining should be station t. They became interested how they should choose these stations s, f, t so that the number Grisha will count is as large as possible. They asked you for help.
The first line contains two integers n and q (2 ≤ n ≤ 105, 1 ≤ q ≤ 105) — the number of stations and the number of days.
The second line contains n - 1 integers p2, p3, ..., pn (1 ≤ pi ≤ n). The integer pi means that there is a route between stations pi and i. It is guaranteed that it's possible to reach every station from any other.
The next q lines contains three integers a, b and c each (1 ≤ a, b, c ≤ n) — the ids of stations chosen by boys for some day. Note that some of these ids could be same.
Print q lines. In the i-th of these lines print the maximum possible number Grisha can get counting when the stations s, t and f are chosen optimally from the three stations on the i-th day.
3 2
1 1
1 2 3
2 3 3
2
3
4 1
1 2 3
1 2 3
2
In the first example on the first day if s = 1, f = 2, t = 3, Misha would go on the route 1 
2, and Grisha would go on the route 3 1 2. He would see the text at the stations 1 and 2. On the second day, if s = 3, f = 2, t = 3, both boys would go on the route 3 1 2. Grisha would see the text at 3 stations.
In the second examle if s = 1, f = 3, t = 2, Misha would go on the route 1 2 3, and Grisha would go on the route 2 3 and would see the text at both stations.
裸的LCA，可是我不会啊，也不会套模板
AA姐太强辣
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const int MAXN=100005; const int DEG=17; vector<int> e[MAXN]; int time_tag,in[MAXN],out[MAXN],dep[MAXN]; int fa[MAXN][DEG]; void dfs(int u) { in[u]=++time_tag; for(int i=1;i<DEG;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=0;i<(int)e[u].size();i++) { int v=e[u][i]; dep[v]=dep[u]+1; fa[v][0]=u; dfs(v); } out[u]=time_tag; } int lca(int u,int v) { if(dep[u]<dep[v])swap(u,v); for(int i=0,d=dep[u]-dep[v];d;i++,d>>=1) if(d&1)u=fa[u][i]; if(u==v)return u; for(int i=DEG-1;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int dis(int u,int v) { return dep[u]+dep[v]-2*dep[lca(u,v)]; } int main() { int n,q; scanf("%d%d",&n,&q); for(int i=2;i<=n;i++) { int p; scanf("%d",&p); e[p].push_back(i); } dfs(1); while(q--) { int k[3]; for(int i=0;i<3;i++) scanf("%d",&k[i]); bool flag=0; for(int i=0;i<3;i++) { int u=k[i],v=k[(i+1)%3],w=k[(i+2)%3],f=lca(u,v); if((lca(u,w)==w || lca(v,w)==w) && in[w]>=in[f] && in[w]<=out[f]) { printf("%d ",max(dis(u,w),dis(v,w))+1); flag=1; break; } } if(!flag) { flag=0; for(int i=0;i<3;i++) { int u=k[i],v=k[(i+1)%3],w=k[(i+2)%3],f=lca(u,v); if(in[w]<in[f] || in[w]>out[f]) { printf("%d ",max({dis(u,f),dis(v,f),dis(w,f)})+1); flag=1; break; } } } if(!flag) { int u=k[0],v=k[1],w=k[2],f=lca(u,v); printf("%d ",max({dis(u,f),dis(v,f),dis(w,f)})+1); } } return 0; }