Codeforces Round 536 (Div. 2)游记

2019.1.31

一次难得的中国场,时间还是在$20:30$,虽然说打到一半,公告$unrated$了,虽然说打到一半$in$ $queue$上$200$页了,但本蒟蒻还是打了下去(都是泪呀)。

说一说比赛概况吧。。。

丑陋的水印↑。
xryjr233虐了。。。

你没看错,rnk1的rqy被我抠了。。。

扯完了,来看一下题目:

A. Lunar New Year and Cross Counting

洛谷链接codeforces链接

题意

给一个$n\times n$的矩阵,这个矩阵由$X$和$.$组成,问在这个矩阵内有多少个图案:

1
2
3
X.X
.X.
X.X

$1\leq n \leq 500$

思路

暴力就好了鸭,但是比赛时不知道哪里打错了。。。交了3次,
都是泪鸭。。。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
char a[710][710];
int n,ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]=='X'&&a[i-1][j-1]=='X'&&a[i-1][j+1]=='X'&&a[i+1][j-1]=='X'&&a[i+1][j+1]=='X'){
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}

B. Lunar New Year and Food Ordering

洛谷链接codeforces链接

题意

一开始,餐厅里有$n$种菜,第$i$种菜有$a_i$份,每份$c_i$元。
现在时除夕夜,有$m$个顾客要来吃饭,第$i$个顾客吃$t_i$种$d_i$份。
如果不够,就补最便宜的,如果真的不够,那么就走人(支付$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
#include<bits/stdc++.h>
#define E 100010
#define ll long long
#define Orz 998244353
using namespace std;
ll n,m,kkk;
struct node{
ll has,cost,id;
}a[E];
ll f[E];
bool cmp(node qx,node qy){
return qx.cost<qy.cost||(qx.cost==qy.cost&&qx.id<qy.id);
}
int main(){
cin>>n>>m;
for(ll i=1;i<=n;i++) cin>>a[i].has;
for(ll i=1;i<=n;i++) cin>>a[i].cost,a[i].id=i;
sort(a+1,a+n+1,cmp);
for(ll i=1;i<=n;i++){
f[a[i].id]=i;
}
kkk=1;
for(ll i=1;i<=m;i++){
ll ci,cn;
cin>>ci>>cn;
if(kkk>n) puts("0");
else{
ll ans=0;
ll bn=min(cn,a[f[ci]].has);
ans+=1ll*a[f[ci]].cost*bn,cn-=bn,a[f[ci]].has-=bn;
if(cn) while(kkk<=n&&cn) bn=min(cn,a[kkk].has),cn-=bn,a[kkk].has-=bn,ans+=1ll*a[kkk].cost*bn,kkk+=(a[kkk].has==0);
cout<<(cn?0ll:ans)<<endl;
}
}
return 0;
}

C. Lunar New Year and Number Division

洛谷链接codeforces链接

题意

将$n$个数字,分成$m$组,使得每一组的数字之和的平方之和最小。
问这个最小值是多少。$n$是偶数。$m$是任意数。

思路

肯定是两两一组啦。。。至于最小嘛肯定是一大一小一组。贪心。
设这$n$个数字为$a_1,a_2,a_3,a_4…a_{n-1},a_n$(按从小到大顺序排列),那么贪心的最小值为:
$$(a_1+a_n)^2+(a_2+a_{n-1})^2…(a_{n/2}+a_{n/2+1})^2$$
即:
$${a_1}^2+{a_2}^2+…{a_n}^2+2\times a_1 \times a_n+2\times a_2 \times a_{n-1}…+2\times a_{n/2}\times a_{n/2+1}$$
因为${a_1}^2+{a_2}^2+…{a_n}^2$是不会变的(更改位置后)
所以只需要比较$\times a_1 \times a_n+2\times a_2 \times a_{n-1}…+2\times a_{n/2}\times a_{n/2+1}$的大小即可,而$2\times a_1 \times a_n+2\times a_2 \times a_{n-1}…+2\times a_{n/2}\times a_{n/2+1}$的最小值必定是$2\times$一大一小(我懒,不证明了),所以最小值肯定为$(a_1+a_n)^2+(a_2+a_{n-1})^2…(a_{n/2}+a_{n/2+1})^2$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[300010];
ll n,ans=0;
int main(){
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(ll i=1;i<=n/2;i++){
ans+=(a[i]+a[n-i+1])*(a[i]+a[n-i+1]);
}
cout<<ans<<endl;
return 0;
}

D. Lunar New Year and a Wander

洛谷链接codeforces链接

题意

求一个无向图的字典序最小的遍历。

思路

因为每个点是可以走重复的,所以肯定使用$bfs$,而又因为是字典序最小的,所以使用堆$priority_queue$,如果本节点确认后就拓展其他相邻的节点。

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
#include<bits/stdc++.h>
#define E 200010
using namespace std;
int n,m;
vector<int> v[E];
int vis[E];
int tt[E];
priority_queue<int,vector<int>,greater<int> > q;
void bfs(int x){
while(!q.empty()) q.pop();
memset(vis,0,sizeof(vis));
memset(tt,0,sizeof(tt));
q.push(x);
while(!q.empty()){
int u=q.top();q.pop();
if(vis[u]==0){cout<<u<<" ";
vis[u]=1;
for(int i=0;i<v[u].size();i++){
int to=v[u][i];

q.push(to);
}}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
}
bfs(1);
return 0;
}

E. Lunar New Year and Red Envelopes

洛谷链接codeforces链接

题意

留个坑以后再填

思路

留个坑以后再填

F. Lunar New Year and a Recursive Sequence

洛谷链接codeforces链接

题意

留个坑以后再填

思路

留个坑以后再填

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×