940和822两套div.2
老规矩
#define MAXN 1000000+5#define MOD 1000000007#define PI (acos(-1.0))#define EPS 1e-6#define MMT(s,a) memset(s, a, sizeof s)#define GO(i,a,b) for(int i = (a); i < (b); ++i)#define GOE(i,a,b) for(int i = (a); i <= (b); ++i)#define OG(i,a,b) for(int i = (a); i > (b); --i)#define OGE(i,a,b) for(int i = (a); i >= (b); --i)
A - Points on the line（940A）
题意：问最少删除几个数字，使得剩余数字的 最大值 - 最小值 < = m；
思路：思维逆向，求符合题意的最多数字
1 #include 2 using namespace std; 3 int a[105]={ 0}; 4 int main(){ 5 int n,d,cnt=-9999999; 6 cin>>n>>d; 7 for(int i=0;i >a[i]; 9 }10 sort(a,a+n);11 for(int i=0;i
B - Our Tanya is Crying Out Loud
题意：从n走到1，两种走法，从n走到n-1，花费a；从n走到n/k，花费b，问最小花费
思路：最开始还想成BFS了，不需要BFS，因为每次都是从n往1走，只需要对比一下下一步两种花费哪种最小就行了。特判一下k==1的情况。
1 int main(){ 2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 3 cin>>n>>k>>a>>b; 4 if(k == 1){ 5 cout << (n-1)*a << endl; 6 } 7 else{ 8 ll ans = 0; 9 while(n > 1){10 if(n%k){11 int m = n%k;12 n -= m;13 if(n<1)14 ans += a*(m-1);15 else16 ans += a*m;17 }18 else{19 int m = n/k;20 if((n-m)*a < b)21 ans += (n-m)*a;22 else23 ans += b;24 n = m;25 }26 }27 cout << ans << endl;28 }29 return 0;30 }
C - Phone Numbers
题意：给你一个长度为n的字符串，然后让你构造一个长度为m的字符串，只能用n中的字符，可重复，输出m的全排列中字典序比n大的第一个。方便理解，我解释一下第一个样例，n = abc，用这个字符串中的元素构成的长度为3的字符串有很多，比如
aaa, aab, aac, aba, abb, abc, aca, acb.......，然后会发现比abc大的第一个就是aca，所以输出aca。
思路：先分两种情况
当n < m时，这时候只需要在n字符串的后面加m-n个最小字符就行了，因为这就是字典序比n字符串大的第一个字符串。
当n >= m时，首先Hash一下n字符串，这时候我们只需要在n字符串中选取m长度的字符串，然后对这个字符串进行+1操作，也就是把字符串看成k进制数，通过前面的Hash表，进行+1，这样就保证了得到的字符串为m长度，而且是大于n字符串的第一个字符串。
1 map Hsh; 2 map Exhsh; 3 int k; 4 char ch1,ch2; 5 6 void gethash(string s){ 7 string ss(s); 8 s.erase(unique(s.begin(),s.end()),s.end()); 9 sort(s.begin(),s.end());10 ch1 = s[0];11 ch2 = s[s.size()-1];12 int len = s.size();13 GO(i,0,len){14 Hsh[s[i]] = i;15 Exhsh[i] = s[i];16 }17 //cout << num << endl;18 }19 20 int main(){21 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);22 int n,m;23 string s;24 cin>>n>>m>>s;25 if(m > n){26 cout << s;27 sort(s.begin(),s.end());28 ch1 = s[0];29 GO(i,n,m){30 cout << ch1;31 }32 cout << endl;33 }34 else{35 gethash(s);36 string ss = s.substr(0,m);37 int flag = 0;38 OGE(i,m-1,0){39 if(i == m-1){40 if(ss[i] < ch2){41 ss[i] = Exhsh[Hsh[ss[i]]+1];42 flag = 0;43 }44 else{45 ss[i] = ch1;46 flag = 1;47 }48 }49 else if(!flag)50 break;51 else{52 if(ss[i] < ch2){53 ss[i] = Exhsh[Hsh[ss[i]]+1];54 flag = 0;55 }56 else{57 ss[i] = ch1;58 flag = 1;59 }60 }61 }62 cout << ss << endl;63 }64 65 return 0;66 }
D - Alena And The Heater
题意就是给你一串a,一串b，然后满足下面关系式
- 当 ai, ai - 1, ai - 2, ai - 3, ai - 4 > r 而且 bi - 1 = bi - 2 = bi - 3 = bi - 4 = 1时，bi = 0
- 当 ai, ai - 1, ai - 2, ai - 3, ai - 4 < l 而且 bi - 1 = bi - 2 = bi - 3 = bi - 4 = 0时， bi = 1
- 其他情况bi = bi - 1
然后就是让你去找一对满足题意的 l 和 r 。
思路：按照题目的要求，不断缩进l和r的范围即可。
1 #include 2 using namespace std; 3 const int maxn=100000+10; 4 const int INF=1e+9; 5 const int NINF=-1e+9; 6 int a[maxn],b[maxn]; 7 string s; 8 int l,r; 9 int main(){10 int n;11 cin>>n;12 l=NINF,r=INF;13 for(int i=0;i >a[i];15 }16 cin>>s;17 for(int i=0;i
F - I'm bored with life
题意：求GCD(a!,b!)；
思路：GCD(a!,b!) = min(a!,b!) = (min(a,b))!;
1 ll f(int n){ 2 if(n == 1) 3 return 1; 4 return n*f(n-1); 5 } 6 7 int main(){ 8 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 9 int a,b;10 cin>>a>>b;11 int n = min(a,b);12 cout << f(n) << endl;13 return 0;14 }
G - Crossword solving
题意：就是当把某个字符换成？就代表可以匹配任何字符，问要使得a串在b串中匹配到，最少需要变几个位置，并输出位置；
思路：暴力找a在b每一个位置需要变换几个字符，并存下位置，然后输出最小变换即可。
#define PB push_back
1 int main(){ 2 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 3 int n,m; 4 int minn = INT_MAX,ii; 5 vector q[1005]; 6 string s1,s2; 7 int num[1005] = { 0}; 8 cin>>m>>n; 9 cin>>s1>>s2;10 GOE(i,0,n-m){11 GO(j,0,m){12 if(s1[j] != s2[i+j]){13 num[i]++;14 q[i].PB(j+1);15 }16 }17 }18 GOE(i,0,n-m){19 if(num[i] < minn){20 minn = num[i];21 ii = i;22 }23 }24 cout << minn << endl;25 for(auto &it:q[ii]){26 cout << it << ' ';27 }28 cout << endl;29 30 return 0;31 }
H - Hacker, pack your bags!
题意：给你一堆时间开始点和结束点，以及花费，问要k小时需要的最小花费，时间不能重叠。
思路：先对所有时间点排序，然后遍历每个时间点的，例如对于第i个，连续时间为x，则去找k-x时间是否存在且满足题意，跟新最小花费，同时用另一个数组维护每个时间段的最小花费。这里排序利用了Tuple的特性所以不需要重构比较函数
#define PB push_back#define MP make_pair#define MT make_tuple
1 vector > op; 2 3 int N, X; 4 int L[210000], R[210000], cost[210000]; 5 6 int dp[210000]; 7 int ans = -1; 8 9 int main(){10 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);11 cin>>N>>X;12 GO(i,0,N){13 cin>>L[i]>>R[i]>>cost[i];14 op.PB(MT(L[i], 0, i));15 op.PB(MT(R[i], 1, i));16 }17 sort(op.begin(), op.end());18 int len = op.size();19 GO(i,0,len){20 int o = get<1>(op[i]), ind = get<2>(op[i]);21 if(o == 0){ //如果是开始时间点22 int dur = R[ind] - L[ind] + 1, nec = X - dur;23 if(nec < 0 || dp[nec] == 0) //如果x-d这段时间不存在24 continue;25 if(ans == -1 || ans > dp[nec] + cost[ind]) //更新花费26 ans = dp[nec] + cost[ind];27 }28 else{ //如果是结束时间点29 int dur = R[ind] - L[ind] + 1;30 if(dp[dur] == 0 || dp[dur] > cost[ind]) //如果这个时间没有使用或者有更小的花费，更新花费31 dp[dur] = cost[ind];32 }33 }34 cout << ans << endl;35 return 0;36 }