2019HPU-ICPC-Training-1

阅读原文时间：2023年07月12日阅读：3

byl太强了，学弟们太强了～全程被吊打，嘤嘤嘤～

A题 Connecting Vertices

http://codeforces.com/problemset/problem/888/F

不会

B题 Local Extrema

http://codeforces.com/problemset/problem/888/A

给一列数字，判断一个数它的左右是否同时比它大，或者同时比它小，若满足的话那么count++，得到最后的count值，那么很明显，直接暴力的遍历一遍就可以了。

C题 Xor-MST

http://codeforces.com/problemset/problem/888/G

不会

D题 Buggy Robot

http://codeforces.com/problemset/problem/888/B

机器人有四种指令，找出在给出的一大串指令中，最多有多少指令是正确的

找到LR和UD有多少对，乘以2就行了

E题 K-Dominant Character

http://codeforces.com/problemset/problem/888/C

给出一个字符串，找出一个最小的长度k，使得每个长度为k的子串中都包含一个相同的字符记录下来每个字符的位置，找两个相同字符的最大距离，对这个最大距离取最小值

1 #include
2 #define ll long long
3 #define ull unsigned long long
4 #define ms(a,b) memset(a,b,sizeof(a))
5 const int inf=0x3f3f3f3f;
6 const ll INF=0x3f3f3f3f3f3f3f3f;
7 const int maxn=1e6+10;
8 const int mod=1e9+7;
9 const int maxm=1e3+10;
10 using namespace std;
11 int main(int argc, char const *argv[])
12 {
13 #ifndef ONLINE_JUDGE
14 freopen("in.txt", "r", stdin);
15 freopen("out.txt", "w", stdout);
16 srand((unsigned int)time(NULL));
17 #endif
18 ios::sync_with_stdio(false);
19 cin.tie(0);
20 string s;
21 cin>>s;
22 int l=s.length();
23 vectorve[30];
24 for(int i=0;i<26;i++)
25 ve[i].push_back(-1);
26 for(int i=0;i<l;i++)
27 ve[s[i]-'a'].push_back(i);
28 for(int i=0;i<26;i++)
29 ve[i].push_back(l);
30 int ans=inf;
31 for(int i=0;i<26;i++)
32 {
33 int res=0;
34 int sz=ve[i].size();
35 for(int j=1;j<sz-1;j++)
36 res=max(res,max(ve[i][j]-ve[i][j-1],ve[i][j+1]-ve[i][j]));
37 if(res==0)
38 continue;
39 ans=min(ans,res);
40 }
41 cout<<ans<<endl;
42 #ifndef ONLINE_JUDGE
43 cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
44 #endif
45 return 0;
46 }

F题 Maximum Subsequence

http://codeforces.com/problemset/problem/888/E

给出n个数，从这n个数中选出几个数（可以不选），使得这些数的和对m取余后的值最大

题解链接：https://www.cnblogs.com/Friends-A/p/11569017.html

1 #include
2 #define ll long long
3 #define ull unsigned long long
4 #define ms(a,b) memset(a,b,sizeof(a))
5 const int inf=0x3f3f3f3f;
6 const ll INF=0x3f3f3f3f3f3f3f3f;
7 const int maxn=1e6+10;
8 const int mod=1e9+7;
9 const int maxm=1e3+10;
10 using namespace std;
11 int a[maxn];
12 int Left[maxn];
13 int Right[maxn];
14 int cntl,cntr;
15 int n,m;
16 int main(int argc, char const *argv[])
17 {
18 #ifndef ONLINE_JUDGE
19 freopen("in.txt", "r", stdin);
20 freopen("out.txt", "w", stdout);
21 srand((unsigned int)time(NULL));
22 #endif
23 ios::sync_with_stdio(false);
24 cin.tie(0);
25 cin>>n>>m;
26 for(int i=0;i>a[i],a[i]%=m;
28 int res=0;
29 int l,r;
30 l=r=n/2;
31 for(int i=0;i<(1<>j&1)
36 res+=a[j],res%=m;
37 Left[cntl++]=res;
38 }
39 res=0;
40 r=n;
41 int num=r-l+1;
42 for(int i=0;i<(1<>j&1)
47 res+=a[l+j],res%=m;
48 Right[cntr++]=res;
49 }
50 Left[cntl++]=0;
51 Right[cntr++]=0;
52 sort(Left,Left+cntl);
53 sort(Right,Right+cntr);
54 cntl=unique(Left,Left+cntl)-Left;
55 cntr=unique(Right,Right+cntr)-Right;
56 int ans=0;
57 for(int i=0;i<cntl;i++)
58 {
59 int res=m-Left[i]-1;
60 int pos=upper_bound(Right,Right+cntr,res)-Right;
61 int num=Right[pos-1];
62 ans=max(ans%m,(num+Left[i])%m);
63 }
64 cout<<ans<<endl;
65 #ifndef ONLINE_JUDGE
66 cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
67 #endif
68 return 0;
69 }

G题 Almost Identity Permutations

http://codeforces.com/problemset/problem/888/D

给出n的全排列，求有多少种排列，满足至少n−k个位置上的数和下标相同（下标从1开始）

错排公式+组合数

题解链接：https://www.cnblogs.com/Friends-A/p/11569153.html

1 #include
2 #define ll long long
3 #define ull unsigned long long
4 #define ms(a,b) memset(a,b,sizeof(a))
5 const int inf=0x3f3f3f3f;
6 const ll INF=0x3f3f3f3f3f3f3f3f;
7 const int maxn=1e6+10;
8 const int mod=1e9+7;
9 const int maxm=1e3+10;
10 using namespace std;
11 ll C(int n,int m)
12 {
13 ll fenmu=1LL;
14 ll fenzi=1LL;
15 for(int i=1;i<=m;i++) 16 { 17 fenmu=1LL*fenmu*(n-i+1); 18 fenzi=1LL*fenzi*i; 19 } 20 return fenmu/fenzi; 21 } 22 int main(int argc, char const *argv[]) 23 { 24 #ifndef ONLINE_JUDGE 25 freopen("in.txt", "r", stdin); 26 freopen("out.txt", "w", stdout); 27 srand((unsigned int)time(NULL)); 28 #endif 29 ios::sync_with_stdio(false); 30 cin.tie(0); 31 int n,k; 32 cin>>n>>k;
33 ll ans=0;
34 if(k>=1)
35 ans+=1;
36 if(k>=2)
37 ans+=(n*(n-1)/2);
38 if(k>=3)
39 ans+=2*C(n,3);
40 if(k>=4)
41 ans+=9*C(n,4);
42 cout<<ans<<endl;
43 #ifndef ONLINE_JUDGE
44 cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
45 #endif
46 return 0;
47 }

H题 Alyona and Spreadsheet

http://codeforces.com/problemset/problem/777/C

给出一个n×m的矩阵，判断第l行～第r行中是否有一列是非递减的

预处理每一行能往上延伸到的位置，注意矩阵的存法

题解链接：https://www.cnblogs.com/Friends-A/p/11569247.html

1 #include
2 #define ll long long
3 #define ull unsigned long long
4 #define ms(a,b) memset(a,b,sizeof(a))
5 const int inf=0x3f3f3f3f;
6 const ll INF=0x3f3f3f3f3f3f3f3f;
7 const int maxn=1e6+10;
8 const int mod=1e9+7;
9 const int maxm=1e3+10;
10 using namespace std;
11 vectorve[maxn];
12 // 当前行能往上延伸的最高位置
13 int can[maxn];
14 // 当前列能往上的最高位置
15 int line[maxn];
16 int main(int argc, char const *argv[])
17 {
18 #ifndef ONLINE_JUDGE
19 freopen("in.txt", "r", stdin);
20 freopen("out.txt", "w", stdout);
21 srand((unsigned int)time(NULL));
22 #endif
23 ios::sync_with_stdio(false);
24 cin.tie(0);
25 int n,m;
26 cin>>n>>m;
27 int x;
28 for(int i=0;i>x,ve[i].push_back(x);
33 for(int i=1;i<=n;i++) 34 { 35 can[i]=i; 36 for(int j=0;j>t;
47 while(t--)
48 {
49 int l,r;
50 cin>>l>>r;
51 if(can[r]>l)
52 cout<<"No\n";
53 else
54 cout<<"Yes\n";
55 }
56 #ifndef ONLINE_JUDGE
57 cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
58 #endif
59 return 0;
60 }

I题 Shell Game

http://codeforces.com/problemset/problem/777/A

现在一共有三个小盒子，其中有一个盒子中有小球.一共进行了n次操作，操作规律有：

①奇数次操作，交换第一个和中间的盒子。

②偶数次操作，交换第三个和中间的盒子。

现在已知操作了n次之后小球在x号盒子中（0,1,2），问初始的时候小球在哪里

循环节，每六个数字一个循环

J题 Hanoi Factory

http://codeforces.com/problemset/problem/777/E

有n个空心圆柱体，第i个圆柱体的内径、外径、高分别为：ai,bi,hi。将这些圆柱体堆起来，要求：从上到下，外径非递减，并且上面的外径小于下面的内径。问最高能堆多高

贪心，用栈维护

题解链接：https://www.cnblogs.com/Friends-A/p/11571769.html

1 #include
2 #define ll long long
3 #define ull unsigned long long
4 #define ms(a,b) memset(a,b,sizeof(a))
5 const int inf=0x3f3f3f3f;
6 const ll INF=0x3f3f3f3f3f3f3f3f;
7 const int maxn=1e6+10;
8 const int mod=1e9+7;
9 const int maxm=1e3+10;
10 using namespace std;
11 struct wzy
12 {
13 int a,b,h;
14 }p[maxn];
15 bool cmp(wzy u,wzy v)
16 {
17 if(u.b==v.b)
18 {
19 if(u.a==v.a)
20 return u.h>v.h;
21 return u.a>v.a;
22 }
23 return u.b>v.b;
24 }
25 int main(int argc, char const *argv[])
26 {
27 #ifndef ONLINE_JUDGE
28 freopen("/home/wzy/in.txt", "r", stdin);
29 freopen("/home/wzy/out.txt", "w", stdout);
30 srand((unsigned int)time(NULL));
31 #endif
32 ios::sync_with_stdio(false);
33 cin.tie(0);
34 int n;
35 cin>>n;
36 for(int i=1;i<=n;i++) 37 cin>>p[i].a>>p[i].b>>p[i].h;
38 sort(p+1,p+1+n,cmp);
39 ll ans=1LL*p[1].h;
40 ll sum=1LL*p[1].h;
41 stackst;
42 st.push(p[1]);
43 for(int i=2;i<=n;i++) 44 { 45 while(!st.empty()&&(st.top().a>=p[i].b||st.top().b<p[i].b))
46 {
47 sum-=1LL*st.top().h;
48 st.pop();
49 }
50 sum+=1LL*p[i].h;
51 st.push(p[i]);
52 ans=max(ans,sum);
53 }
54 cout<<ans<<endl;
55 #ifndef ONLINE_JUDGE
56 cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
57 #endif
58 return 0;
59 }

K题 Cloud of Hashtags

http://codeforces.com/contest/777/problem/D

n个字符串，要求不改变位置，删除最少的字符串的后缀，使这些字符串按照字典序非递减的顺序排列

暴力即可

题解链接：https://www.cnblogs.com/Friends-A/p/11569328.html

1 #include
2 #define ll long long
3 #define ull unsigned long long
4 #define ms(a,b) memset(a,b,sizeof(a))
5 const int inf=0x3f3f3f3f;
6 const ll INF=0x3f3f3f3f3f3f3f3f;
7 const int maxn=1e6+10;
8 const int mod=1e9+7;
9 const int maxm=1e3+10;
10 using namespace std;
11 vectorve;
12 vectorans;
13 int get_place(string s1,string s2)
14 {
15 int l1=s1.length();
16 int l2=s2.length();
17 int i;
18 for(i=0;is2[i])
25 return i;
26 }
27 if(i==l2)
28 {
29 if(l1>l2)
30 {
31 if(s1[i-1]==s2[i-1])
32 return l2;
33 else
34 return l1;
35 }
36 }
37 return l1;
38 }
39 int main(int argc, char const *argv[])
40 {
41 #ifndef ONLINE_JUDGE
42 freopen("in.txt", "r", stdin);
43 freopen("out.txt", "w", stdout);
44 srand((unsigned int)time(NULL));
45 #endif
46 ios::sync_with_stdio(false);
47 cin.tie(0);
48 int n;
49 cin>>n;
50 string s;
51 for(int i=0;i>s;
54 ve.push_back(s);
55 }
56 string s1,s2;
57 ans.push_back(ve[n-1]);
58 for(int i=n-2;i>=0;i--)
59 {
60 s1=ve[i];
61 s2=ans[n-(i+2)];
62 int pos=get_place(s1,s2);
63 string ss;
64 ss=s1.substr(0,pos);
65 ans.push_back(ss);
66 }
67 for(int i=n-1;i>0;i--)
68 cout<<ans[i]<<endl;
69 cout<<ve[n-1]<<endl;
70 #ifndef ONLINE_JUDGE
71 cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
72 #endif
73 return 0;
74 }

L题 Game of Credit Cards

http://codeforces.com/contest/777/problem/B

Sherlock和Moriarty有n张卡片，每个卡片上有一个数字，现在有Sherlock和Moriarty 两个人在比较这些卡片上的数字大小，小的数字需要接受惩罚，Sherlock的卡片顺序是固定的，Moriarty的卡片顺序可以随意变动，求Moriarty的最小接受惩罚次数是多少，Sherlock最大惩罚对方的次数是多少

排序比较即可

题解链接：https://www.cnblogs.com/Friends-A/p/11569436.html

1 #include
2 #define ll long long
3 #define ull unsigned long long
4 #define ms(a,b) memset(a,b,sizeof(a))
5 const int inf=0x3f3f3f3f;
6 const ll INF=0x3f3f3f3f3f3f3f3f;
7 const int maxn=1e6+10;
8 const int mod=1e9+7;
9 const int maxm=1e3+10;
10 using namespace std;
11 int s[maxn],m[maxn];
12 int nums[100],numm[100];
13 int main(int argc, char const *argv[])
14 {
15 #ifndef ONLINE_JUDGE
16 freopen("in.txt", "r", stdin);
17 freopen("out.txt", "w", stdout);
18 srand((unsigned int)time(NULL));
19 #endif
20 ios::sync_with_stdio(false);
21 cin.tie(0);
22 int n;
23 string s1,s2;
24 cin>>n;
25 cin>>s1>>s2;
26 for(int i=0;i=n&&pos2>=n)
37 break;
38 while(pos1<n&&m[pos1]<s[i])
39 pos1++;
40 while(pos2<n&&m[pos2]<=s[i])
41 pos2++;
42 if(pos1<n)
43 res1++,pos1++;
44 if(pos2<n)
45 res2++,pos2++;
46 }
47 cout<<n-res1<<endl;
48 cout<<res2<<endl;
49 #ifndef ONLINE_JUDGE
50 cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
51 #endif
52 return 0;
53 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

2015长春 HDU 5534 Partial Tree

Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) C.Producing Snow

HDU 6203 2017沈阳网络赛 LCA，DFS+树状数组

【bzoj3576】 Hnoi2014—江南乐

主席树+二分 p4602

hdu6138（后缀数组）

【dp】 AreYouBusy

GSS4 D - Can you answer these queries IV

hdu2825（AC 自动机）

synchronized中wait、notify的原理与源码