凌晨的阳光懒洋洋的，总是很舒服的。

嘴里嚼过冰，胸口渗过汗，身体追过风，眼睛交换过光阴，如此才算夏天一场。

img

牛客周赛 Round 16

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
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n - 1; i++) {
        b[i] = a[i + 1] - a[i];
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] <= a[i - 1]) {
            cout << "No\n";
            return 0;
        }
    }
    for (int i = 1; i <= n - 2; i++) {
        if (b[i] <= b[i + 1]) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
    }

B

注意向上取整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    int x, y;
    cin >> x >> y;
    int r = ceil(sqrt(x * x + y * y));
    if (r >= 11)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << min(10, 11 - r) << endl;
    }
    return 0;
}

C

二维偏序问题，

可以先过滤掉一定不符合的元素，

然后排序，按照血量大和攻击力来排序，

然后直接LIS即可。

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
#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define endl "\n"
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0)
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int main()
{
    int n, H, A; 
    cin >> n >> H >> A;
    vector<PII> p(n + 1);
    for(int i = 0; i < n; i ++) cin >> p[i].first;
    for(int i = 0 ;i < n; i ++) cin >> p[i].second;
    vector<PII> bkp;
    for(int i = 0; i < n; i ++)
    {
        if(p[i].first < H && p[i].second < A)
            bkp.pb(p[i]);
    }
    //排序
    sort(bkp.begin(), bkp.end(), [](PII a, PII b)
         {
             if(a.first == b.first) return a.second > a.second;
             return a.first > b.first;
         });
    int m = bkp.size();
    int res = 0;
     
    vector<int> dp(m, 1);
    for(int i = 0; i < m; i ++)
    {
        for(int j = 0; j < i; j ++)
        {
            if(bkp[i].first < bkp[j].first && bkp[i].second < bkp[j].second)
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << endl;
    return 0;
}

D

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200010;
struct node{
	int u,v,w,num;
}e[N];
int n,m,fa[N],vis[N];
int find(int u)
{
	if(fa[u]!=u) return fa[u]=find(fa[u]);
	return u;
}
int ans,cnt,tot;
int cmp(node a,node b)
{
	return a.w<b.w;
}
void kruskal()
{
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int a=find(e[i].u);
		int b=find(e[i].v);
		if(a==b) continue;
		ans+=e[i].w;
		vis[e[i].num]=1;
		tot++;
		fa[a]=b;
	}
}
int a,b,c,d;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c>>d;
		if(d==1){
			fa[find(a)]=find(b);
			vis[i]=1;
			tot++;
		}
		e[i].u=a,e[i].v=b,e[i].w=c,e[i].num=i;
	}
	kruskal();
    if(tot<n-1) cout<<"-1";
    else
    {
        cout<<tot<<endl;
        for(int i=1;i<=m;i++)
        {
            if(vis[i]) cout<<i<<' ';
         } 
    }
	return 0;
}
img