2024ICPC杭州vp
题目链接：2024ICPC杭州
A
签到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
}
int find(vector<int> &f, int x) {
return (x == f[x] ? x : f[x] = find(f, f[x]));
}
void solve(){
string s1, s2, s3;
cin >> s1 >> s2 >> s3;
vector<int> f(30, 0);
for(int i = 1; i < 30; i++) {
f[i] = i;
}
if(s1.size() != s2.size()) {
cout << "NO\n";
return;
}
if(s1.size() != s3.size()) {
cout << "YES\n";
return;
}
for(int i = 0; i < s1.size() && i < s2.size(); i++) {
f[find(f, s1[i]-'a'+1)] = find(f, s2[i]-'a'+1);
}
bool ok = false;
for(int i = 0; i < s1.size() && i < s3.size(); i++) {
if(find(f, s1[i]-'a'+1) != find(f, s3[i]-'a'+1)) {
ok = true;
break;
}
}
if(ok) {
cout << "YES\n";
return;
}
cout << "NO\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
K
枚举每个数，记录它的行出现的次数，当次数加k大于等于m时取max(i,k)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e5+5;
const int MOD=998244353;
const int INF=1e18;
int n,m,k;
int a[N];
int vis[N];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
fr(i,n*m){
vis[i]=0;
a[i]=0;
}
}
void solve(){
cin>>n>>m>>k;
fr(i,n*m){
cin>>a[i];
a[i]=(a[i]-1)/m+1;
}
fr(i,n*m){
vis[a[i]]++;
if(vis[a[i]]+k>=m){
cout<<max(i,m)<<"\n";
init();
return;
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
H
显然当所有链的长度都一样时，不可行，现在思考如何让其可行。
可以看出，若最长链为n，必须存在长度小于等于n-2的链，才能使最长链确定。
最长链确定后，图就是确定的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
struct chain {
int size,l,r;
};
bool operator< (chain a,chain b)
{
return a.size<b.size;
}
void init(){
}
void solve(){
int n,k;
cin>>n>>k;
vector<chain> a(k);
for(int i=0;i<k;i++)
{
cin>>a[i].l>>a[i].r;
a[i].size=a[i].r-a[i].l+1;
}
sort(a.begin(),a.end());
if(k!=1&&a[k-1].size-a[0].size<=1&&a[k-1].size==a[k-2].size)
{
cout<<"IMPOSSIBLE\n";
return;
}
int maxsize=a[k-1].size;
vector<int> b(n+1);
b[a[k-1].l]=0;
for(int i=a[k-1].l+1;i<=a[k-1].r;i++)
{
b[i]=i-1;
}
for(int i=0;i<k-1;i++)
{
if(a[i].size==maxsize)
b[a[i].l]=maxsize-a[i].size+a[k-1].l;
else
b[a[i].l]=maxsize-a[i].size+a[k-1].l-1;
for(int j=a[i].l+1;j<=a[i].r;j++)
{
b[j]=j-1;
}
}
for(int i=1;i<=n;i++)
{
cout<<b[i]<<" ";
}
cout<<"\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
E
我们想要让电梯尽量只消耗必须运人的花费，显然当电梯到达r的最大值时可以做到，我们要想的是如何让电梯到达r的最大值。
电梯从出发点p出发，每次选择的$[l,r]$应满足$pos>=l,r>=pos$，这样只消耗r-l就能往上走。
当没有符合条件的$l,r$时选择上方最近的$l,r$，这样就能花费最小代价到达最高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<int>
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n,pos;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
inline void Add(int& x,int y){
x+=y;
if(x>=MOD)x%=MOD;
}
int Mul(int x,int y){
x*=y;
if(x>=MOD)x%=MOD;
return x;
}
void init(){
}
void solve(){
cin>>n>>pos;
vector<array<int,3>>a(n);
vector<int>vis(n+5,0);
int ans=0;
vec sum;
for(int i=0;i<n;i++){
cin>>a[i][0]>>a[i][1];
a[i][2]=i+1;
}
sort(a.begin(),a.end());
for(int i=0;i<n;i++){
auto [u,v,id]=a[i];
if(pos>=u&&v>=pos){
pos=v;
ans+=v-u;
sum.push_back(id);
vis[id]=1;
}
else if(u>pos){
ans+=u-pos;
ans+=v-u;
pos=v;
sum.push_back(id);
vis[id]=1;
}
}
sort(a.begin(),a.end(),[&](array<int,3>a,array<int,3>b){return a[1]>b[1];});
for(int i=0;i<n;i++){
auto [u,v,id]=a[i];
if(vis[id]==0){
ans+=v-u;
sum.push_back(id);
}
}
cout<<ans<<endl;
for(auto i:sum){
cout<<i<<' ';
}
cout<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
|
M
首先需要猜出结论：只需要满足一个数与其左边第一个小于它的数组成的集合和与它右边第一个小于它的数组成的集合即可。怎么证明就不写了。
观察到对于1，1e18这样的pair，只有19个数符合条件，大概率对于任意pair，符合条件的数不超50个。那么我们只需要求出一个pair的数，然后在别的pair上验证即可。
对于$k(x+cnt)=y+cnt$，可化简为$cnt=(y-x)/(k-1)-x$。我们只需枚举k-1，然后判断它满不满足即可。显然，只需枚举到$\sqrt{y-x}$即可，因为对于可整除的一个k-1，(y-x)/(k-1)也可被整除
复杂度：$O(T\sqrt{1e9}+50*2n)$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<long long>
#define lowbit(x) ((x)&(-x))
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n,k;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
long long ksm(long long a, long long b) {
long long res = 1;
while(b) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
inline void Add(int &x,int y){((x+=y)>=MOD)?(x-=MOD):0;}
int Mul(int x,int y){return (x*y+MOD)%MOD;}
void init(){
}
void solve(){
cin>>n>>k;
vec b(n+1,0);
stack<int>idx;
vecp pi;
fr(i,n)cin>>b[i];
fr(i,n){
while(!idx.empty()&&b[i]<idx.top()){
pi.push_back({b[i],idx.top()});
idx.pop();
}
idx.push(b[i]);
}
while(!idx.empty()){
idx.pop();
}
for(int i=n;i>=1;i--){
while(!idx.empty()&&b[i]<idx.top()){
pi.push_back({b[i],idx.top()});
idx.pop();
}
idx.push(b[i]);
}
if(pi.empty()){
cout<<k<<' '<<k*(k+1)/2<<endl;
return;
}
auto [u,v]=pi.front();
int g=v-u;
vec sum;
for(int i=1;i*i<=g;i++){
if(g%i==0){
if(g/i-u>=1&&g/i-u<=k){
sum.push_back(g/i-u);
}
if(g/(g/i)-u>=1&&g/(g/i)-u<=k&&g/i!=i){
sum.push_back(g/(g/i)-u);
}
}
}
vec ans;
for(auto x:sum){
int c=1;
for(auto [a,b]:pi){
if((b+x)%(a+x)!=0){
c=0;
break;
}
}
if(c)ans.push_back(x);
}
cout<<ans.size()<<' '<<accumulate(ans.begin(),ans.end(),(int)0)<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
|