Codeforces Round 895 (Div. 3) A-F

A. Two Vessels

签到

#include

using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
int mod=998244353;
const int maxv=4e6+5;

void solve()
{
	int a,b,c;
	cin>>a>>b>>c;
	int x=abs(a-b);
	int ans=(x+c*2-1)/(c*2);
	cout<<ans<<endl;

}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	while(t--){
		solve();
	}
    system("pause");
    return 0;
}
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

B. The Corridor or There and Back Again

思路：考虑对于每个炸弹，到达该位置后，在给定时间内能走过的最远距离。

#include

using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
int mod=998244353;
const int maxv=4e6+5;



void solve()
{
	int n;
	cin>>n;
	vector<pll> a(n);
	for(int i=0;i<n;i++){
		int d,s;
		cin>>d>>s;
		a[i]={d,s};
	}
	sort(a.begin(),a.end());
	ll sum=2e9;
	for(int i=0;i<n;i++){
		auto [x,y]=a[i];
		sum=min(sum,x+(y-1)/2);
	}
	cout<<sum<<endl;
}







int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	while(t--){
		solve();
	}
    system("pause");
    return 0;
}
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

C. Non-coprime Split

思路：对于一个大于2的偶数$x$，我们一定能将其分解为$x+（x-2）$的形式，所以大于二的偶数一定合法，那么考虑奇数的情况，对于奇数$y$，如果其有一个不为本身且不为1的因子，那么我们一定能将其分解为$y+(y-2)$的形式。

综上所述：

对于一个区间$[l,r]$,如果$l-r>=1$,并且合法的偶数不为2的情况下，那么我们一定可以选择这个区间中的某个偶数。

如果$l==r$，那么我们只需要对其进行质因数分解判断是否存在合法的质因子。

#include
using namespace std;
const int N=1e7+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
int mod=998244353;
const int maxv=4e6+5;

void solve()
{
	int l,r;
	cin>>l>>r;
	if(l!=r){
		if(r%2!=0){
			r--;
		}
		if(r-2!=0) {
			cout<<2<<" "<<r-2<<endl;
			return ;
		}
		else {
			cout<<-1<<endl;
			return ;
		}
	}
	else{
		for(int i=2;i*i<=l;i++){
			if(l%i==0&&l/i>1){
				cout<<i<<" "<<l-i<<endl;
				return ;
			}
		}
	}
	cout<<-1<<endl;
}







int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	//ol();
	while(t--){
		solve();
	}
    system("pause");
    return 0;
}
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

D. Plus Minus Permutation

思路：因为n的数据范围很大，所以考虑这题是否跟结论挂钩。考虑所有$x$位置和$y$位置对答案的贡献，因为总贡献为$x$的贡献减去$y$的贡献，我们贪心的想，尽可能把大的数放在的位置，把小的数放在的位置，但对于$x$和$y$可能存在位置重合的情况，那么对于这种情况，该位置对答案的贡献为0。现在考虑如何求解$x$和$y$的贡献。

我们其实可以O（1）的算出$x$位置的个数和$y$位置的个数，同时我们也可以算出来重合位置的个数，因为所有重合位置的坐标即为x和y的最小公倍数，最后进行贡献计算即可。

#include

using namespace std;
const int N=1e7+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
int mod=998244353;
const int maxv=4e6+5;

void solve()
{
	ll n,x,y;
	cin>>n>>x>>y;
	ll l=lcm(x,y);
	int cnt=n/l;
	ll c1=n/x;
	ll c2=n/y;
	c1-=cnt;
	c2-=cnt;
	ll sum=0;
	sum+=(n-c1+1+n)*c1/2;
	sum-=(1+c2)*c2/2;
	cout<<sum<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	ol();
	while(t--){
		solve();
	}
    system("pause");
    return 0;
}
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

E. Data Structures Fan

题意：

给你一个整数数组$a_1,a_2,\dots ,a_n$，以及一个由$n$个字符组成的二进制字符串由 $n$个字符组成。

给定 $q$个询问。询问有两种类型：

• “1 $l$ $r$”（$1\le l\le r\le n$）–用相反的字符替换$l\le i\le r$的每个字符$s_i$。即用$\text{1}$替换所有$\text{0}$，用$\text{0}$替换所有$\text{1}$。

• “2 $g$” ( g ∈ { 0 , 1 } g \in \{0, 1\} g∈{0,1}) - 计算所有索引 $i$ 的数字 $a_i$ 的 bitwise XOR 的值，使得 $s_i=g$。注意，空数集的$\mathrm{XOR}$被认为等于$0$
  给你一个整数数组$a_1,a_2,\dots ,a_n$，以及一个由$n$个字符组成的二进制字符串$3$由 $n$个字符组成。

例如，如果$n=4$，$a=[1,2,3,6]$，$s=\text{1001}$，请考虑下面一系列的疑问：

1. “2 $0$”–我们感兴趣的是$s_i=0$的索引$i$，因为$s=1001$，这些索引是索引$2$和$3$，所以查询的答案将是$a_2\oplus a_3=2\oplus 3=1$。
2. “1 $1$ $3$”–我们需要将字符$s_1,s_2,s_3$替换为它们的对立面，因此查询前为$s=1001$，查询后为$s=0111$：$s=0111$.
3. “2$1$”–我们感兴趣的是$s_i=1$的索引$i$，因为$s=0111$，这些索引就是$2$、$3$和$4$，所以查询的答案将是$a_2\oplus a_3\oplus a_4=2\oplus 3\oplus 6=7$。
4. “1 $2$ $4$” - $s=0111$ $\to$ $s=0000$.
5. “2$1$” - $s=0000$，没有带$s_i=1$的索引，所以因为空数集的$\mathrm{XOR}$被认为等于$0$，所以这个查询的答案是$0$。

${}^{†}$二进制字符串是指只包含字符$\text{0}$或$\text{1}$的字符串。

思路：
法一：运用异或相关的性质。
比如给定数组$a_1,a_2,a_3,a_4,a_5$,给定字符串为$01110$，我们可以先计算出$s_i$等于1的值，为$a_2\oplus a_3\oplus a_4$,同样，我们可以计算出$s_i$等于0的值，为$a_1\oplus a_5$。
考虑修改操作，我们可以先预处理出来数组的异或前缀和，还是以上文为例，为：$a_1\oplus a_2\oplus a_3\oplus a_4\oplus a_5$,我们如果对区间$[4,5]$进行修改，修改后字符串变为$01101$,值为1的结果为$a_2\oplus a_3\oplus a_5$,我们会发现，我们原来1的结果为$a_2\oplus a_3\oplus a_4$，我们和区间$[4,5]$的异或值进行异或,为$a_2\oplus a_3\oplus a_4\oplus a_4\oplus a_5$,即为$a_2\oplus a_3\oplus a_5$；对于0的情况也同理。

#include

using namespace std;
const int N=1e7+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
int mod=998244353;
const int maxv=4e6+5;


void solve()
{
	int n;
	cin>>n;
	vector<ll> a(n+5);
	vector<ll> s(n+5);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]^a[i];
	}
	string st;
	cin>>st;
	st=" "+st;
	ll tot=s[n];
	ll tot1=0;
	ll tot2=0;
	for(int i=1;i<=n;i++){
		if(st[i]=='1') tot1^=a[i];
		else tot2^=a[i];
	}
	int q;
	cin>>q;
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int l,r;
			cin>>l>>r;
			ll val=s[l-1]^s[r];
			tot1^=val;
			tot2^=val;
		}
		else{
			int g;
			cin>>g;
			if(g==1){
				cout<<tot1<<" ";
			}
			else{
				cout<<tot2<<" ";
			}
		}
	}
	cout<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	//ol();
	while(t--){
		solve();
	}
    system("pause");
    return 0;
}
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

法二：线段树板子
思路：我们使用线段树，对于线段树的每个节点，我们储存两个值，分别为节点所在区间的在二进制字符串中为0的异或值的和与1的异或值的和。然后进行正常的区间修改和查询即可。具体思路看代码注释

#include
using namespace std;
const int N=1e5+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
int mod=998244353;
const int maxv=4e6+5;

struct node
{
	int l,r,b[2],tag;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define tag(x) tr[x].tag
	#define b0(x) tr[x].b[0]
	#define b1(x) tr[x].b[1]
} tr[N*4];
string s;
int a[N];

void update(int p)
{
	b0(p)=b0(p*2)^b0(p*2+1);
	b1(p)=b1(p*2)^b1(p*2+1);
}

void bulid(int p,int l,int r)
{
	if(l==r){
		l(p)=l,r(p)=r;
		if(s[l]=='1'){
			tr[p].b[1]=a[l];
			tr[p].b[0]=0;
		} 
		else {
			tr[p].b[0]=a[l];
			tr[p].b[1]=0;
		}
		tag(p)=0;
		return ;
	}
	l(p)=l,r(p)=r,b0(p)=b1(p)=tag(p)=0;
	int mid=(l+r)/2;
	bulid(p*2,l,mid);
	bulid(p*2+1,mid+1,r);
	update(p);
}

void pushdown(int p)//pushdown和modify中同理，把子节点进行交换
{
	if(tag(p)){
		swap(b0(p*2),b1(p*2));
		swap(b0(p*2+1),b1(p*2+1));
		tag(p*2)^=1;
		tag(p*2+1)^=1;
	}
	tag(p)=0;
}

void modify(int p,int l,int r)
{
	if(l<=l(p)&&r(p)<=r){
		swap(b0(p),b1(p));//修改把区间中储存的0和1进行交换即可
		tag(p)^=1;
		return ;
	}
	pushdown(p);
	int mid=(l(p)+r(p))/2;
	if(l<=mid) modify(p*2,l,r);
	if(r>mid) modify(p*2+1,l,r);
	update(p);
}

int query(int p,int l,int r,int f)//query函数其实不用写，因为这题的查询相当于查询区间[1,n]
{
	if(l<=l(p)&&r(p)<=r){
		if(f==1) return b1(p);
		else return b0(p);
	}
	pushdown(p);
	int mid=(l(p)+r(p))/2;
	int res=0;
	if(l<=mid) res^=query(p*2,l,r,f);
	if(r>mid) res^=query(p*2+1,l,r,f);
	return res;
}


void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>s;
	s=" "+s;
	bulid(1,1,n);
	int q;
	cin>>q;
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int l,r;
			cin>>l>>r;
			modify(1,l,r);
		}
		else{
			int g;
			cin>>g;
			cout<<query(1,1,n,g)<<" ";
		}
	}
	cout<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	//ol();
	while(t--){
		solve();
	}
    system("pause");
    return 0;
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

F. Selling a Menagerie

题意：您是一个动物园的主人，动物园里有$n$只动物，编号从$1$到$n$。然而，维持动物园的费用相当昂贵，因此您决定出售动物园！

众所周知，每只动物都害怕另一只动物。更确切地说，动物 $i$害怕动物 $a_i$（$a_i\ne i$）。另外，每只动物的成本是已知的，对于动物 $i$来说，成本等于 $c_i$。

您将按固定顺序出售所有动物。从形式上看，您需要选择某种排列【1011】，先卖出动物 $p_1$，然后卖出动物 $p_2$，以此类推，最后卖出动物 $p_n$。

当你卖出动物$i$时，有两种可能的结果：

• 如果动物 $a_i$是在动物 $i$之前***卖出的，那么你卖出动物 $i$会得到 $c_i$元钱。
• 如果动物$a_i$在动物$i$之前***没有卖出，那么卖出动物$i$可以得到$2\cdot c_i$金钱。 令人惊讶的是，目前害怕的动物更值钱）。

你的任务是选择出售动物的顺序，使总利润最大化。

例如，如果$a=[3,4,4,1,3]$，$c=[3,4,5,6,7]$，而你选择的排列顺序是$[4,2,5,1,3]$，那么：

• 第一只出售的动物是动物 $4$。动物 $a_4=1$以前没有卖过，所以卖掉它你可以得到 $2\cdot c_4=12$元钱。
• 第二只要出售的动物是动物 $2$。动物$a_2=4$之前已经卖出，所以卖出它你会得到$c_2=4$金钱。
• 第三只要出售的动物是动物$5$。动物 $a_5=3$之前没有卖出过，所以卖出它你会得到 $2\cdot c_5=14$金钱。
• 第四只要出售的动物是动物 $1$。动物 $a_1=3$之前没有卖出过，所以卖出它你会得到 $2\cdot c_1=6$金钱。
• 第五只要出售的动物是动物 $3$。动物$a_3=4$之前被卖掉了，所以卖掉它你可以得到$c_3=5$金钱。

在这种排列方式下，你的总利润为 $12+4+14+6+5=41$。请注意，在这个例子中，$41$并不是***可能的最大利润。

${}^{†}$长度为$n$的排列是一个数组，由$n$个不同的整数组成，这些整数从$1$到$n$依次排列。例如，$[2,3,1,5,4]$是一个排列，但$[1,2,2]$不是排列（$2$在数组中出现两次），$[1,3,4]$也不是排列（$n=3$，但$4$在数组中出现）。

思路：拓扑排序。
动物 $i$害怕动物 $a_i$，并且对于第$i$个动物，动物 $a_i$没有在它前面卖出，那么我们的收获会越大，所以我们贪心的想，让对于每一个$i$，我们贪心的认为，让所有令$i$害怕的动物全部在$i$后进行售卖。对$i$和$a_i$进行连边，那么就转为了求在该图下的拓扑序列，但又因为存在环，所以我们需要断环为链，我们同样贪心的想，我们想让断环为链的损失最小，所以我们找到价值最小的那个动物x，然后让令x害怕的那个动物排在第一位即可，因为这样整个环只有价值最小的那个动物以价格$c_i$卖出。具体注释看代码。

#include

using namespace std;
const int N=1e5+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<int,4> p4;
int mod=998244353;
const int maxv=4e6+5;

vector<int> e[N];
int d[N],st[N];//st数组用于标记已经在拓扑序中的点
int n;
vector<int> a(N),c(N);
vector<int> ans;
int val=2e9,idx=0;
void add(int u,int v)
{
	e[u].push_back(v);
}

void dfs(int x)
{
	st[x]=1;
	for(auto u: e[x]){
		if(c[u]<val){
			val=c[u],idx=u;
		}
		if(!st[u]){
			dfs(u);
		}
		else return;
	}
}

void topsort()//拓扑排序板子
{
	queue<int >q;
	for(int i=1;i<=n;i++) {
		if(d[i]==0) q.push(i);
	}
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		st[t]=1;
		ans.push_back(t);
		for(auto x: e[t]){
			d[x]--;
			if(d[x]==0) q.push(x);
		}
	}
}

void solve()
{
	cin>>n;
	memset(st,0,(n+5)*sizeof (int));
	memset(d,0,(n+5)*sizeof (int));
	for(int i=1;i<=n;i++) {
		e[i].clear();
	}
	ans.clear();
	for(int i=1;i<=n;i++ ){
		cin>>a[i];
		add(i,a[i]);
		d[a[i]]++;
	}
	for(int i=1;i<=n;i++) cin>>c[i];
	topsort();//拓扑序进行完毕，再考虑断环为
	for(int i=1;i<=n;i++){//dfs找环上价值最小的点
		if(!st[i]){
			val=2e9,idx=0;
			dfs(i);
			int x=a[idx];//最先放入x的后继
			do{
				ans.push_back(x);
				x=a[x];
			}while(x!=a[idx]);
		}
	}
	for(auto x: ans) cout<<x<<" ";
	cout<<endl;
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	while(t--){
		solve();
	}
	system("pause");
	return 0;
}
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
97
98
99

​