ACM团队周赛题解(3)

简介: 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...

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 <bits/stdc++.h>
 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<n;i++){
 8         cin>>a[i];
 9     }
10     sort(a,a+n);
11     for(int i=0;i<n;i++){
12         for(int j=0;j<n;j++){
13             if(a[j]-a[i]<=d) cnt=max(cnt,j-i+1);
14         }
15     }
16     cout<<n-cnt<<endl;
17     return 0;
18 }

 

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                 else
16                     ans += a*m;
17             }
18             else{
19                 int m = n/k;
20                 if((n-m)*a < b)
21                     ans += (n-m)*a;
22                 else
23                     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<char,int> Hsh;
 2 map<int,char> 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 <bits/stdc++.h>
 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<n;i++){
14         cin>>a[i];
15     }
16     cin>>s;
17     for(int i=0;i<s.size();i++){
18         b[i]=s[i]-'0';
19     }
20     for(int i=4;i<n;i++){
21         if(b[i]==1&&b[i-1]==0&&b[i-2]==0&&b[i-3]==0&&b[i-4]==0){
22             l=max(l,max(a[i]+1,max(a[i-1]+1,max(a[i-2]+1,max(a[i-3]+1,a[i-4]+1)))));
23      }
24         else if(b[i]==0&&b[i-1]==1&&b[i-2]==1&&b[i-3]==1&&b[i-4]==1){
25             r=min(r,min(a[i]-1,min(a[i-1]-1,min(a[i-2]-1,min(a[i-3]-1,a[i-4]-1)))));
26         }
27     }
28     cout<<l<<" "<<r<<endl;
29     return 0;
30 }

 

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<int> 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<tuple<int,int,int>> 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 }

 

目录
相关文章
|
数据安全/隐私保护
ACM刷题之路(四)2018暑假实验室集训——深广搜专题题解
ACM刷题之路(四)2018暑假实验室集训——深广搜专题题解
ACM刷题之路(十八)二分 2019暑期集训 POJ 3579 Median
ACM刷题之路(十八)二分 2019暑期集训 POJ 3579 Median
|
人工智能 算法
【ACM】—蓝桥杯大一暑期集训Day4
【ACM】—蓝桥杯大一暑期集训Day4
92 0
|
算法
【ACM】—蓝桥杯大一暑期集训Day1
【ACM】—蓝桥杯大一暑期集训Day1
106 0
|
算法
【ACM】—蓝桥杯大一暑期集训Day2
【ACM】—蓝桥杯大一暑期集训Day2
91 0
|
算法
【ACM】—蓝桥杯大一暑期集训Day3
【ACM】—蓝桥杯大一暑期集训Day3
105 0
|
算法
【ACM】—蓝桥杯大一暑期集训Day5
【ACM】—蓝桥杯大一暑期集训Day5
90 0
|
机器学习/深度学习 C++
ACM刷题之路(十七)二分 2019暑期集训 POJ2785
ACM刷题之路(十七)二分 2019暑期集训 POJ2785
ACM刷题之路(十九)二分+尺取 2019暑期集训 HDU6231 K-th Number
ACM刷题之路(十九)二分+尺取 2019暑期集训 HDU6231 K-th Number
ACM刷题之路(二十一)大素数筛选 2019暑期集训 POJ 2689 Prime Distance
ACM刷题之路(二十一)大素数筛选 2019暑期集训 POJ 2689 Prime Distance

热门文章

最新文章