链接：https://ac.nowcoder.com/acm/contest/392/A
来源：牛客网
华华听月月唱歌
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
月月唱歌超级好听的说！华华听说月月在某个网站发布了自己唱的歌曲，于是把完整的歌曲下载到了U盘里。然而华华不小心把U盘摔了一下，里面的文件摔碎了。月月的歌曲可以看成由1到N的正整数依次排列构成的序列，它现在变成了若干个区间，这些区间可能互相重叠。华华想把它修复为完整的歌曲，也就是找到若干个片段，使他们的并集包含1到N（注意，本题中我们只关注整数，见样例1）。但是华华很懒，所以他想选择最少的区间。请你算出华华最少选择多少个区间。因为华华的U盘受损严重，所以有可能做不到，如果做不到请输出-1。
输入描述:
第一行两个正整数N、M，表示歌曲的原长和片段的个数。
接下来M行，每行两个正整数L、R表示第i的片段对应的区间是[L,R]。
输出描述:
如果可以做到，输出最少需要的片段的数量，否则输出-1。
示例1
输入
复制
4 2 1 2 3 4
输出
复制
2
示例2
输入
复制
4 2 1 1 3 4
输出
复制
-1
示例3
输入
复制
10 5 1 1 2 5 3 6 4 9 8 10
输出
复制
4
备注:
5
贪心每个区间，先进行自定义排序。
一开始原来数据就有坑，后面wa了三次，系统提醒A题改描述了，（气死
然后改一下条件就A了
1 #include <bits/stdc++.h> 2 #define N 100050 3 #define ll long long int 4 using namespace std; 5 struct Node{ 6 ll l,r; 7 }node[N]; 8 bool cmp(Node a, Node b){ 9 if(a.l == b.l) 10 return a.r > b.r; 11 return a.l < b.l; 12 } 13 ll n, m, mod; 14 int main(){ 15 cin >> n >> m; 16 for(int i = 0; i < m; i++){ 17 cin >> node[i].l >> node[i].r; 18 } 19 sort(node, node+m, cmp); 20 int k = 0; 21 int last = 0; 22 int end = 0; 23 for(int i = 0; i < m; i++){ 24 if(end+1 >= node[i].l && node[i].r > end){ 25 if(node[i].l > last){ 26 last = end; 27 k++; 28 } 29 end = node[i].r; 30 } 31 if(end >= n) 32 break; 33 if(node[i].l > end+1){ 34 break; 35 } 36 } 37 if(end < n){ 38 cout<<"-1"<<endl; 39 }else{ 40 cout<<k<<endl; 41 } 42 return 0; 43 }
链接：https://ac.nowcoder.com/acm/contest/392/B
来源：牛客网
华华教月月做数学
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
找到了心仪的小姐姐月月后，华华很高兴的和她聊着天。然而月月的作业很多，不能继续陪华华聊天了。华华为了尽快和月月继续聊天，就提出帮她做一部分作业。
月月的其中一项作业是：给定正整数A、B、P，求ABmodP的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程序，所以这个任务就交给你了。
因为月月的作业很多，所以有T组询问。
输入描述:
第一行一个正整数T表示测试数据组数。
接下来T行，每行三个正整数A、B、P，含义如上文。
输出描述:
输出T行，每行一个非负整数表示答案。
示例1
输入
复制
2 2 5 10 57284938291657 827493857294857 384729583748273
输出
复制
2 18924650048745
备注:
18
这题一看就果断用了python写
不用怕大数
1 def pow_mod(a, b, mod): 2 ans = 1 3 while b > 0: 4 if b&1: 5 ans = (ans*a)%mod 6 b >>= 1 7 a = (a*a)%mod 8 return ans%mod 9 10 n = int(input()) 11 for i in range (0, n): 12 lis = list(map(int, input().split())) 13 print(pow_mod(lis[0], lis[1], lis[2]))
链接：https://ac.nowcoder.com/acm/contest/392/E
来源：牛客网
华华给月月准备礼物
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
输入描述:
第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行N个正整数Li表示每根木棍的初始长度。
输出描述:
输出一行一个非负整数表示每根木棍的最大长度。
示例1
输入
复制
5 10 4 4 4 5 3
输出
复制
1
说明
如果长度为2，只能得到2+2+2+2+1=9根，不够；长度为1可以得到4+4+4+5+3=20根，足够。所以答案最大是1。
示例2
输入
复制
5 3 1 2 3 4 5
输出
复制
3
备注:
9
这题一开始想用优先队列模拟，写了一半发现思路完全错了。
然后果断改用二分找最优值。
1 #include <bits/stdc++.h> 2 #define N 200050 3 #define ll long long int 4 using namespace std; 5 ll an[N]; 6 ll n, m; 7 int main(){ 8 cin >> n >> m; 9 ll sum = 0; 10 for(int i = 0; i < n; i++){ 11 cin >> an[i]; 12 sum += an[i]; 13 } 14 sum /= m; 15 ll cnt = 0; 16 ll l = 1, r = sum; 17 while(l <= r){ 18 ll mid = (r+l)>>1; 19 ll ans = 0; 20 for(int i = 0; i < n; i++){ 21 ans += an[i]/mid; 22 } 23 if(ans >= m){ 24 l = mid + 1; 25 cnt = mid; 26 }else{ 27 r = mid - 1; 28 } 29 } 30 cout<<cnt<<endl; 31 return 0; 32 }
链接：https://ac.nowcoder.com/acm/contest/392/G
来源：牛客网
华华对月月的忠诚
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
月月要参加学校的信息学集训，晚上不能陪华华聊天了。不过为了防止华华去和别的小姐姐聊天，浪费时间影响学习，所以月月给华华布置了一项任务。月月给了华华一个类似斐波那契数列的东西，这个数列满足：
gcd(FN,FN+1)。月月认为，求这个东西需要很长的时间，所以华华就没有机会去和其他小姐姐聊天了。华华自然对月月十分忠诚，选择求出F的每一位后计算答案。但是比赛中的你看到这一题，就没必要那么老实了。现在给定A、B、N，请你求出月月要求的那个数字。答案可能很大，但是不取模。
输入描述:
输入一行三个正整数A，B，N。
输出描述:
输出一行一个正整数表示答案。
示例1
输入
复制
2 4 5
输出
复制
2
说明
F序列如下：2，4，6，10，16，26，……
第N项16和第N+1项26的最大公约数为2，故答案输出2。
备注:
5
这个就找到规律，可以推出来
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 long long int n,m; 5 string s; 6 int main(){ 7 cin >> n >> m >> s; 8 cout<<__gcd(n,m)<<endl; 9 return 0; 10 }
链接：https://ac.nowcoder.com/acm/contest/392/I
来源：牛客网
华华和月月逛公园
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
月月和华华一起去逛公园了。公园很大，为了方便，可以抽象的看成一个N个点M条边的无向连通图（点是景点，边是道路）。公园唯一的入口在1号点，月月和华华要从这里出发，并打算参观所有的景点。因为他们感情很好，走多远都不会觉得无聊，所以所有景点和道路都可以无数次的重复经过。月月发现，有些路可走可不走，有些路则必须要走，否则就无法参观所有的景点。现在月月想知道，有几条路是不一定要经过的。因为这是个很正常的公园，所以没有重边和自环。
输入描述:
第一行两个正整数N和M，表示点数和边数。
接下来M行，每行两个正整数U和V表示一条无向边。
保证给定的图是连通的。
输出描述:
输出一行一个非负整数表示不一定要经过的边有几条。
示例1
输入
复制
5 5 1 2 2 3 3 4 4 5 3 5
输出
复制
3
说明
例如第三条边，月月和华华可以依次走过第一条、第二条、第五条、第四条边走过全部的景点，所以第三条边不一定要经过。同理还有第四条、第五条边，答案为3。
备注:
5
这个是赛后补题，
这个求桥的tarjin算法确实好用。
1 #include <bits/stdc++.h> 2 #define N 500005 3 using namespace std; 4 vector<int> v[N]; 5 int dfn[N], low[N], vis[N], bridge[N], b[N]; 6 int ans = 0, times; 7 stack<int> s; 8 9 void tarjin(int t, int u){//u表示父节点，仅用于防止回走 10 dfn[t] = low[t] = times++; 11 s.push(t); 12 for(int i = 0; i < v[t].size(); i++){ 13 if(!dfn[v[t][i]]){ 14 tarjin(v[t][i], t); 15 low[t] = min(low[t], low[v[t][i]]); 16 if(dfn[t] < low[v[t][i]]){ 17 ans += !bridge[v[t][i]]; 18 bridge[v[t][i]] = 1; 19 } 20 } 21 if(dfn[v[t][i]] && v[t][i] != u) 22 low[t] = min(low[t], dfn[v[t][i]]); 23 } 24 if(low[t] == dfn[t]){ 25 while(s.top() != t){ 26 s.pop(); 27 } 28 s.pop(); 29 } 30 } 31 32 int main(){ 33 int n, m, q; 34 while(cin >> n >> m){ 35 memset(b,0,sizeof(b)); 36 while(!s.empty()) 37 s.pop(); 38 times = 1; 39 int x, y; 40 for(int i = 0; i < m; i++){ 41 cin >> x >> y; 42 v[x].push_back(y); 43 v[y].push_back(x); 44 } 45 for(int i = 1; i <= n; i++) 46 if(!dfn[i]) 47 tarjin(i, 0); 48 cout << m - ans << endl; 49 } 50 return 0; 51 }
链接：https://ac.nowcoder.com/acm/contest/392/J
来源：牛客网
月月查华华的手机
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
月月和华华一起去吃饭了。期间华华有事出去了一会儿，没有带手机。月月出于人类最单纯的好奇心，打开了华华的手机。哇，她看到了一片的QQ推荐好友，似乎华华还没有浏览过。月月顿时醋意大发，出于对好朋友的关心，为了避免华华浪费太多时间和其他网友聊天，她要删掉一些推荐好友。但是为了不让华华发现，产生猜疑，破坏了他们的友情，月月决定只删华华有可能搭讪的推荐好友。
月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪，当且仅当小姐姐的昵称是他的昵称的子序列。为了方便，华华和小姐姐的昵称只由小写字母构成。为了更加方便，保证小姐姐的昵称长度不会比华华的长。
现在月月要快速的判断出哪些推荐好友要删掉，因为华华快回来了，时间紧迫，月月有点手忙脚乱，所以你赶紧写个程序帮帮她吧！
输入描述:
第一行输入一个字符串A表示华华的昵称。
第二行输入一个正整数N表示华华的推荐好友的个数。
接下来N行，每行输入一个字符串Bi表示某个推荐好友的昵称。
输出描述:
输出N行，对于第i个推荐好友，如果华华可能向她搭讪，输出Yes，否则输出No。
注意大写，同时也要注意输出效率对算法效率的影响。
示例1
输入
复制
noiauwfaurainairtqltqlmomomo 8 rain air tql ntt xiaobai oiiiooo orzcnzcnznb ooooo
输出
复制
Yes Yes Yes Yes No Yes No No
备注:
6
此题做的最傻逼，。。。。。
开始跟同学讨论一下，竟然提出用字典树模拟，
当时应该脑子也冲了，没想那么多，就按照那个思路写了，
结果样例都显示段错误，然后仔细分析一下自己是怎么存的，
然后发现是长度的阶乘个空间再乘26.。。。
我擦，，，n^n次方的复杂度几乎。。。（笑哭，当时怎么这么蠢
然后赛后看了一眼通过的代码，我擦，二分大法好啊！！我咋没想到。。
然后再看一个，！！！我特么，这个代码纯暴力怎么可能可以过，
然后两个人仔细研究一番，确定就是纯暴力。
然后就吐槽了一下出题人的数据怎么这么水，纯暴力的复杂度可是O（ 10^12）
1 #include <bits/stdc++.h> 2 #define ll long long int 3 using namespace std; 4 5 vector<int> v[30]; 6 7 string s, ss; 8 int n; 9 int main(){ 10 cin >> s; 11 for(int i = 0; i < s.length(); i++){ 12 int an = s[i] - 'a'; 13 v[an].push_back(i); 14 } 15 cin >> n; 16 while(n--){ 17 int end = -1; 18 bool prime = true; 19 cin >> ss; 20 for(int i = 0; i < ss.length(); i++){ 21 int an = ss[i] - 'a'; 22 int len = v[an].size(); 23 int pos = upper_bound(v[an].begin(), v[an].end(), end) - v[an].begin(); 24 if(pos == v[an].size()){ 25 prime = false; 26 break; 27 } 28 end = v[an][pos]; 29 } 30 if(prime){ 31 cout<<"Yes"<<endl; 32 }else{ 33 cout<<"No"<<endl; 34 } 35 } 36 37 return 0; 38 }