ACM

题目链接 题意： # 求矩形周长并。 思路： # 线段树+扫描线。 和前面的求面积并比较类似，我们先考虑平行x轴的线段，考虑线段树，维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len.

题目链接 题意： # 求n（1000）个矩形的面积交，也就是至少有2个矩形覆盖的区域的面积。 思路： # 和矩形面积并_hdu1542解题报告 类似

hdu1542题目链接 题意： # 求n(100)个矩形的面积并。 思路： # 扫描线+线段树 题目是2000年中欧区域赛的题目，虽然年代久远，但是有好几个点还是很值得学习的。

zoj3606题目链接 题意：有个小女孩卖火柴，有n个人会来买，分别在时间t[i]，以价格p[i]，买的火柴个数为1+(k-1)%3，其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴，小女孩就会睡着。小女孩睡着后如果有人来买火柴，那小女孩就会醒过来，但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。

题目链接 题意：n（1E5）个操作，分为三种，add x表示将x加到集合中（保证集合中之前没有x)，del x表示从集合中删掉x（保证集合中一定有x）,sum表示求集合中所有元素按从小到大排列后，所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9

题目链接 题意：给出n,p,q,r，以及n（1E5）个数，所有数的范围都是[-1E9,1E9]，现在问p_a[i]+q_a[j]+r*a[k]的最大值，满足1<=i<=j<=k<=n

题目链接 题意：有若干线段，给出起点和终点，问是否有一个线段是冗余的。冗余的意思是说，对于该线段所覆盖的所有整数点，没有该线段，也能被其他一个或者多个线段覆盖到。如果有，输出任意一个冗余线段即可。

比赛链接 10个月没写题了，菜啊。进行一点恢复性训练好了。 A: 给一个数，可以在填写若干（或者0）个前缀0，问能否变成回文数。 思路是直接删掉后面可能的出现的0再判断回文数就好。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年09月24日 星期日 13时51分06秒 4File Name :A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define PB push_back 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28 29using namespace std; 30const double eps = 1E-8; 31const int dx4[4]={1,0,0,-1}; 32const int dy4[4]={0,-1,1,0}; 33const int inf = 0x3f3f3f3f; 34bool check( int x) 35{ 36 vector<int>val; 37 while (x) 38 { 39 int tmp = x; 40 val.push_back(tmp); 41 x/=10; 42 } 43 int siz = val.size(); 44 if (siz==1) return true; 45 for ( int i = 0 ; i < siz/2 ; i++) 46 { 47 if (val[i]!=val[siz-1-i]) return false; 48 } 49 return true; 50} 51int main() 52{ 53 #ifndef ONLINE_JUDGE 54 //freopen("./in.txt","r",stdin); 55 #endif 56 int x; 57 cin>>x; 58 while(x==0) 59 { 60 x/=10; 61 } 62 if (check(x)) puts("YES"); 63 else puts("NO"); 64 65 66 #ifndef ONLINE_JUDGE 67 fclose(stdin); 68 #endif 69 return 0; 70} B: 2*n个人，每个人的重量为w[i]，要分成n-1组，每组2个人，以及2个单独的人。单独的人的不稳定性为0，每组的不稳定是该组的2个人的重量的差的绝对值。总的不稳定为所有组的不稳定性之和。问可能的最小不稳定性是多少。

请实现最近最少使用缓存(Least Recently Used (LRU) cache)类，需要支持 get, set，操作。 get 操作，给出 key，获取到相应的 value (value 为非负数)，如果不存在返回-1, 如果存在此 key 算作被访问过。 set 操作，设置 key，如果 key 存在则覆盖之前的 value (此时相当于访问过一次)。 如果 key 不存在，需要进行插入操作，如果此时已经 key 的数量已经到达 capacity, 这样需要淘汰掉最近最少使用(也就是上次被使用的时间距离现在最久的)的那 一项。

题目链接 题意： # 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。 思路： # 暴力即可orz(数据是真的水啊。

题目链接 题意： # 给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。 思路： # LCA还是一下就能想到的，rmq+dfs在线求。

题目链接 题意： # 给出由小写字母，’?‘和’*‘组成的字符串s，仅由小写字母组成的字符串t，问按照规则s能否变成t.

题意：k^D=n(%p)，求最小的D (1<=K, P, N<=10^9) 思路：出题人英文水平捉鸡。。。。 扩展BSGS算法即可，注意p>=n的时候显然是无解的，判掉。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :Mon 24 Jul 2017 09:43:41 PM CST 4File Name :2815.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define PB push_back 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28 29using namespace std; 30const double eps = 1E-8; 31const int dx4[4]={1,0,0,-1}; 32const int dy4[4]={0,-1,1,0}; 33const int inf = 0x3f3f3f3f; 34LL k,p,n; 35map<LL,LL>mp; 36LL ksm(LL a,LL b,LL p) 37{ 38 LL res = 1LL; 39 while (b) 40 { 41 if (b&1) res = res * a % p; 42 b = b>>1LL; 43 a = a * a % p; 44 } 45 return res; 46} 47LL gcd( LL a,LL b){return b?gcd(b,a%b):a;} 48LL BSGS(LL a,LL b,LL p) 49{ 50 a%=p; 51 b%=p; 52 // if (a==0&&b==0) return 0; 53 // if (a==0) return -1; 54 if (b==1) return 0; 55 int cnt = 0 ; 56 LL t = 1; 57 for (int g = gcd(a,p); g!=1 ; g = gcd(a,p)) 58 { 59 if (b%g) return -1; 60 p/=g; 61 b/=g; 62 t=t*a/g%p; 63 cnt++; 64 if (b==t) return cnt; 65 } 66 mp.clear(); 67 int m = ceil(sqrt(double(p))); 68 LL base = b ; 69 for ( LL i = 0 ; i < m ; i++) 70 { 71 mp[base] = i; 72 base = base * a % p; 73 } 74 base = ksm(a,m,p); 75 LL ret = t ; 76 for ( int i = 1 ; i <= m+1 ; i++) 77 { 78 ret = ret * base % p; 79 if (mp.count(ret)) return i*m-mp[ret]+cnt; 80 } 81 return -1; 82} 83int main() 84{ 85 #ifndef ONLINE_JUDGE 86 freopen("./in.txt","r",stdin); 87 #endif 88 while (~scanf("%lld%lld%lld",&k,&p,&n)) 89 { 90 if (n>=p) 91 { 92 puts("Orz,I can’t find D!"); 93 continue; 94 } 95 if (p==1) 96 { 97 puts("Orz,I can’t find D!"); 98 continue; 99 } 100 LL ans = BSGS(k,n,p); 101 if (ans==-1) puts("Orz,I can’t find D!"); 102 else printf("%lld\n",ans); 103 } 104 105 #ifndef ONLINE_JUDGE 106 fclose(stdin); 107 #endif 108 return 0; 109}

Description # 已知数a,p,b，求满足a^x≡b(mod p)的最小自然数x。 Input # 每个测试文件中最多包含100组测试数据。 每组数据中，每行包含3个正整数a,p,b。 当a=p=b=0时，表示测试数据读入完全。 Output # 对于每组数据，输出一行。 如果无解，输出“No Solution”（不含引号），否则输出最小自然数解。 Sample Input # 5 58 33 2 4 3 0 0 0

离散对数（Discrete Logarithm）问题是这样一个问题，它是对于模方程 a^x=b(mod prime)，求满足条件的X，或者得出不存在这样的X 最暴力的思路，那么就是枚举x? 根据费马小定理，只需要枚举[0,p-1)

题目链接 题意： Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that BL == N (mod P) 思路：bsgs算法 详情见BSGS算法笔记 然后被map的count坑了一下？ 我想判断map中某个key是否存在，用count会TLE，find也会TLE,[]可以通过….不太懂，复杂度不都是log吗，差常数？还是有人会退化？

题目链接 题意：有２种货币，分别为C和D.给出n种资源的代价和美丽度，每种资源只能用其中一种资源购买。现在拥有货币C的数量是c，拥有货币D的数量是d.然后恰好买２个资源，问最大美丽度，不能的话输出０．

题目链接 题意：有n个Ｔ恤，每个价格都不同，有三种颜色，分别用1,2,3表示，每件Ｔ恤给出前xiong和后背的颜色。现在有m个顾客排成一队，对于每个顾客，给出他喜欢的颜色，只要一个Ｔ恤的前xiong或者后背的颜色之一满足该颜色即可。顾客总希望买符合他喜欢颜色的Ｔ恤中价格最低的。现在问每个顾客买到的Ｔ恤的价格，如果某个顾客没有买Ｔ恤，输出-1

题目链接 题意：初始有一个锅，每t分钟可以做好k个饼，现在需要N个饼。还可以另外建一个锅，花费d时间，建好以后两个锅可以并行烙饼。问是否应该建锅？（以期减少烙饼时间） 思路：求出两种情况下的总时间，比较一下。

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.