8 题【我：3、队友：3+2】。实话说能摸到 silver 确实让我很惊讶。希望之后的比赛能有好运吧。其实之前校赛铁 + 篮球杯省2= 和 CF 一直绿名上不去，确实对于我的信心造成了一定的影响，还有之前的西部邀请赛也打的稀烂，还有天梯赛也是真的 1 拖 4。之前也打过团队 VP，但是题目切的非常艰难，一度非常忧郁，觉得太菜了。

昨天个人 VP 能摸到 bronze，今天团队 VP 甚至有 golden 的希望（现场大概 rank 15）。平时还是看到开一点吧！个人实力和团队实力其实没有那么不堪。所以真心希望下半年的 icpc 可以打出成绩。

A&K

队友切的签到。（K 题我手速太慢了，本来让我切的

不过有时候还是需要看一下队友的代码学习一下的，所以这里还是贴一下队友的代码。

A 简单枚举 by Ping

#include<bits/stdc++.h>

using namespace std;

void work(){

int k,ans=0;

cin>>k;

for(int i=1;i<=6;i++){

for(int j=i;j<=6;j++){

if(i+j==k)ans++;

}

cout<<ans<<endl;

}

int main(){

int t;

cin>>t;

while(t--){

work();

}

// Created by johntime on 24-5-9.

K 简单贪心 by john

#include <bits/stdc++.h>

using namespace std;

bool appear[1000000]={0};

void solve()

{

int n,k;

cin >> n >> k;

int first=1;

int cnt=0;

while (cnt<n)

{

for (int i=first;i<=n;i+=k)

{

cnt++;

appear[i]=1;

printf("%d ",i);

}

while (appear[first])

first++;

}

int main()

{

//ios::sync_with_stdio(0);

//cin.tie(0); cout.tie(0);

//int t; cin >> t;

//for (;t;t--)

solve();

return 0;

}

M

模拟+贪心。比较简单的题。

#include <bits/stdc++.h>

using LD = long double;

int main() {

std::ios::sync_with_stdio(false);

std::cin.tie(nullptr);

std::cout.tie(nullptr);

// freopen("m.in", "r", stdin);

int n, k, x, p0;

std::cin >> n >> k >> x >> p0;

std::vector<int> s(n + 1);

std::vector<int> p(k + 1), t(k + 1);

for (int i = 1; i <= n; ++ i) std::cin >> s[i];

for (int i = 1; i <= k; ++ i) std::cin >> t[i];

for (int i = 1; i <= k; ++ i) std::cin >> p[i];

std::sort(s.begin() + 1, s.end());

int res = 0;

LD time = 0;

for (int pos = n, i = 1; pos and i <= n; ++ i) {

while (pos and (LD)x / s[pos] <= (p0 - time)) ++ res, -- pos;

if (t[i] > p0) break;

time = t[i];

p0 = p[i];

}

std::cout << res << '\n';

}

D&B&E

模拟，队友切的。实话说能有可以信任的队友真的是非常好的感觉。

你可以觉得大家都是最好的状态，大家也都是互相依靠的关系。就算这题切不出来，也会有人在你的背后。无论是否尽如人意，大家永远在一起比赛。

D 模拟 by ping

#include <bits/stdc++.h>

using namespace std;

#define INF 1<<30

long long count_score(long long b,long long d2,long long d1,long long d0)

{

if (b==0)

return INF;

long long ret=0;

if (b<d2)

return b;

b-=d2;

ret+=d2;

if (b<d1)

return ret;

b-=d1;

if (b<d0)

return ret-b;

return ret-d0;

}

void d_count(long long &b,long long &d2,long long &d1,long long &d0)

{

if (b<d2)

{

d2-=b;

b=0;

return;

}

b-=d2;

d2=0;

if (b<d1)

{

d1-=b;

b=0;

return;

}

b-=d1;

d1=0;

if (b<d0)

{

d0-=b;

b=0;

return;

}

b-=d0;

d0=0;

return;

}

void solve()

{

long long br,bp,bs;

long long dr,dp,ds;

long long ans=0;

cin >> br >> bp >> bs;

cin >> dr >> dp >> ds;

long long sr,sp,ss;

while (br+bp+bs>0)

{

sr=count_score(br,dp,dr,ds);

sp=count_score(bp,ds,dp,dr);

ss=count_score(bs,dr,ds,dp);

long long min_s=sr,p=1;

if (sp<min_s)

{min_s=sp; p=2;}

if (ss<min_s)

{min_s=ss; p=3;}

if (min_s==INF)

break;

ans+=min_s;

switch(p)

{

case 1:

d_count(br,dp,dr,ds);

break;

case 2:

d_count(bp,ds,dp,dr);

break;

case 3:

d_count(bs,dr,ds,dp);

break;

}

cout << ans << '\n';

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0); cout.tie(0);

int t; cin >> t;

for (;t;t--)

solve();

return 0;

}

B 模拟 by John

#include<bits/stdc++.h>

using namespace std;

void work(){

int n,k,m;

cin>>n>>k>>m;

vector<int> a(n,0);

map<int,int> mp;

for (int i = 0; i < n; ++i) {

cin>>a[i];

}

vector<vector<int>> same(k+1);

for(int i=0;i<n;i++){

same[a[i]].push_back(i);

}

int cir=m/n,lst=m%n;

vector<int> ans(n,0);

for(int i=1;i<=k;i++){

if(same[i].size()%2==0){

for(int j=1;j<same[i].size();j+=2){

ans[same[i][j]]+=cir;

}

}else{

for(auto &j:same[i]){

ans[j]+=cir/2;

}

int rst=cir%2;

for(int j=1;j<same[i].size();j+=2){

ans[same[i][j]]+=rst;

}

if(rst)mp[i]=1;

}

for(int i=0;i<lst;++i){

if(mp[a[i]]==0){

mp[a[i]]=1;

}else{

ans[i]++;

mp[a[i]]=0;

}

for(int i=0;i<n-1;i++){

cout<<ans[i]<<' ';

}

cout<<ans[n-1]<<endl;

}

int main(){

int t;

cin>>t;

while(t--)work();

}

// Created by johntime on 24-5-9.

E 图论 by ping。忽然发现这题赛时只有 26 个队过，队友疑似有点太强了。

#include <bits/stdc++.h>

using namespace std;

struct planet{

set<int> e;

int m;

};

int find_path(vector<planet> &p,stack<int> &lp,int f)

{

//printf("\tsearch %d: %d\n",f,p[f].m);

//for (auto i:p[f].e)

// printf("\t\t%d --- %d\n",f,i);

if (p[f].e.size()==0 || p[f].m<=f)

{

if (!lp.size())

return 1;

for (int n=lp.top();;n=lp.top())

if (p[n].e.size()==0 || p[n].m<=f)

{

lp.pop();

if (lp.empty())

break;

continue;

}

else

{

if (p[n].e.count(f+1))

return 0;

return 1;

}

return 1;

}

else

{

if (p[f].e.count(f+1))

return 0;

return 1;

}

void solve()

{

int n,m,u,v;

cin >> n >> m;

vector<planet> p(n+10);

p[0].m=0;

for (int i=0;i<m;i++)

{

cin >> u >> v;

//if (u<v)

p[u].e.insert(v);

p[u].m=v>p[u].m?v:p[u].m;

//else if (v<u)

p[v].e.insert(u);

p[v].m=u>p[v].m?u:p[v].m;

}

long long ans=0;

int temp;

stack<int> lp;

for (int nowp=1;nowp<n;nowp++)

{

while (lp.size() && p[lp.top()].m<nowp)

lp.pop();

if (p[nowp-1].e.size() && p[nowp-1].m>nowp)

lp.push(nowp-1);

temp=find_path(p,lp,nowp);

ans+=temp;

}

cout << ans << '\n';

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0); cout.tie(0);

int t; cin >> t;

for (;t;t--)

solve();

return 0;

}

H

分类讨论，模拟。不过在中国人出的题目里看英文学日语语法做模拟题真的难绷。

#include <bits/stdc++.h>

std::pair<int, int> type(std::string s) { // type len

std::reverse(s.begin(), s.end());

std::string pre3 = s.substr(4, 3);

std::string pre2 = s.substr(4, 2);

if (pre3 == "ihs") return {5, 7};

if (pre2 == "ig") return {4, 6};

if (pre2 == "ik") return {3, 6};

if (pre2 == "im" or pre2 == "in" or pre2 == "ib") return {2, 6};

if (pre3 == "ihc") return {1, 7};

if (pre2 == "ir") return {1, 6};

return {1, 5};

}

std::string type_add(int x) {

if (x == 1) return "tte";

if (x == 2) return "nde";

if (x == 3) return "ite";

if (x == 4) return "ide";

return "shite";

}

void solve() {

std::string s;

std::cin >> s;

if (s == "ikimasu") {

std::cout << "itte\n";

return;

}

auto [t, len] = type(s);

std::cout << s.substr(0, s.size() - len) + type_add(t) << '\n';

}

int main() {

std::ios::sync_with_stdio(false);

std::cin.tie(nullptr);

std::cout.tie(nullptr);

// freopen("h.in", "r", stdin);

int T;

std::cin >> T;

while (T --) {

solve();

}

L

虚拟原点+bfs求最短路。不过一开始我用的是 dijkstra，然后 T 了。一直想不明白怎么回事，以为是卡常了（因为这题要做 100 次，所以我觉得我常数太大了），后来才知道是复杂度错了。因为边权只有 1，所以正常 BFS 求就可以。这样就把 log 的复杂度去掉了。

#include <bits/stdc++.h>

using PII = std::pair<int, int>;

constexpr int INF = 0x3f3f3f3f;

template<typename T>

void chkmin(T &a, const T &b) {

if (a > b) a = b;

}

void solve() {

int n, m, q;

std::cin >> n >> m >> q;

std::vector<int> w(n + 1);

for (int i = 1; i <= n; ++ i) {

std::cin >> w[i];

}

std::vector<std::vector<int>> G(n + 1);

std::vector<std::vector<int>> st_w(101);

for (int i = 1; i <= n; ++ i) {

st_w[w[i]].push_back(i);

}

auto add_edge = [&](int a, int b) {

G[a].push_back(b);

};

for (int i = 1; i <= m; ++ i) {

int u, v;

std::cin >> u >> v;

add_edge(u, v);

add_edge(v, u);

}

std::vector<std::vector<int>> dist(101, std::vector<int>(n + 1, INF));

auto calc_dist = [&](int st, std::vector<int> &dist) -> void {

std::queue<PII> q;

std::vector<bool> vis(n + 1, false);

for (auto u : st_w[st]) {

q.emplace(0, u);

dist[u] = 0;

}

while (q.size()) {

auto [d, u] = q.front();

q.pop();

if (vis[u]) continue;

vis[u] = true;

for (auto v : G[u]) {

if (vis[v]) continue;

chkmin(dist[v], d + 1);

q.emplace(dist[v], v);

}

};

for (int i = 1; i <= 100; ++ i) {

calc_dist(i, dist[i]);

}

while (q --) {

int pos, max_val;

std::cin >> pos >> max_val;

int res = INF;

for (int i = 1; i <= max_val; ++ i) {

chkmin(res, dist[i][pos]);

}

if (res == INF) res = -1;

std::cout << res << '\n';

}

int main() {

std::ios::sync_with_stdio(false);

std::cin.tie(nullptr);

std::cout.tie(nullptr);

int T = 1;

while (T --) {

solve();

}

C&F&J

和队友最后在思考的题目，C 是一道计算几何，求质心，很多细节判断。

F 题一开始我觉得是一个贪心，但是数据范围很奇怪：无向图 $n\le 300,m\le 300$，看上去不像贪心也不像 DP，看题解才发现是一个网络流（哭了，队里没人会）。

J 题是一个需要思维的模拟，但是队友的做法好像假了，但是已经很接近答案了。

补题的时候看题解发现这个碰撞问题其实可以直接看成穿过。这样看的话周期就比较明显。然后两边使用队列维护，最后记录最后一只掉落的时间加上之前循环的次数即可。

#include <bits/stdc++.h>

using LL = long long;

using LD = long double;

template<typename T>

void chkmax(T &x, const T &y) {

if (x < y) x = y;

}

void solve() {

int n, cntA, cntB;

std::cin >> n >> cntA >> cntB;

std::vector<int> a(n + 1), d(n + 1);

for (int i = 1; i <= n; ++ i) std::cin >> a[i];

for (int i = 1; i <= n; ++ i) std::cin >> d[i];

int leftmost = 0, rightmost = 1e9 + 1;

std::vector<std::queue<LL>> q(2); // 维护每个点到墙壁的距离

for (int i = 1; i <= n; ++ i) if (d[i] == 0) q[0].push(a[i] - leftmost);

for (int i = n; i; -- i) if (d[i] == 1) q[1].push(rightmost - a[i]);

// 对于两个墙壁来说

// 可能的情况是

// 1. 0 先被摧毁

// 2. 1 先被摧毁

// 3. 0 和 1 同时被摧毁

int Length = rightmost - leftmost;

int Time = 2 * Length; // 一个周期内所以蚂蚁都回到原来的位置每个挡板发生n次碰撞

int cnt_turn = std::min(cntA / n, cntB / n);

cntA -= cnt_turn * n;

cntB -= cnt_turn * n;

LL ans = (LL)cnt_turn * Time;

LL lastTime0 = 0, lastTime1 = 0; // 维护每个方向最后一个掉下来的蚂蚁的时间

auto act0 = [&]() -> void {

auto a0 = q[0].front(); q[0].pop();

if (cntA) {

cntA --;

q[1].push(a0 + Length);

} else {

chkmax(lastTime0, a0);

}

};

auto act1 = [&]() -> void {

auto a1 = q[1].front();

q[1].pop();

if (cntB) {

cntB --;

q[0].push(a1 + Length);

} else {

chkmax(lastTime1, a1);

}

};

while (cntA and cntB) act0(), act1();

if (cntA) { // l 墙还未摧毁这时有可能 l 墙未摧毁而所有蚂蚁都已经掉下来

while (cntA and q[0].size()) act0();

if (cntA) { // 这说明所有蚂蚁都从 r 墙掉下来

while (q[1].size()) act1();

} else { // 这说明两边都有蚂蚁掉下来

while (q[1].size()) act1();

while (q[0].size()) act0();

}

} else { // r 墙还未摧毁

while (cntB and q[1].size()) act1();

if (cntB) { // 这说明所有蚂蚁都从 l 墙掉下来

while (q[0].size()) act0();

} else { // 这说明两边都有蚂蚁掉下来

while (q[0].size()) act0();

while (q[1].size()) act1();

}

ans += std::max(lastTime0, lastTime1);

std::cout << ans << '\n';

}

int main() {

std::ios::sync_with_stdio(false);

std::cin.tie(nullptr);

std::cout.tie(nullptr);

int T = 1;

while (T --) {

solve();

}

【团队VP】2021 四川省赛

A&K

M

D&B&E

H

L

C&F&J

发表回复取消回复

【团队VP】2021 四川省赛

A&K

M

D&B&E

H

L

C&F&J

发表回复 取消回复

发表回复取消回复