西北大学第四届程序设计竞赛新生赛

第四届程序设计竞赛新生赛"/>

西北大学第四届程序设计竞赛新生赛

题目链接：
题解链接：.html

文章目录

• A - 1e9个兵临城下
• B - 抢课啦!
• C - ICPC-无限路之城
• D - 赌神
• G - 卖萌型选手
• I - 曾有你的森林,あなたがいた森
• L - 鸡尾酒买罐子

A - 1e9个兵临城下

利用到了容斥原理，注意数据需要开成long long

#include <cstdio>
#include <iostream>
using namespace std;
const int n = 1e9;
typedef long long ll;int main(void)
{ll t, a1, a2, a3, a12, a13, a23, a123;ll a, b, c, ans;scanf("%lld", &t);while (t--){scanf("%lld%lld%lld", &a, &b, &c);a1 = n / a;a2 = n / b;a3 = n / c;a12 = n / (a * b);a13 = n / (a * c);a23 = n / (b * c);a123 = n / (a * b * c);ans = a1 + a2 + a3 - a12 - a13 - a23 + a123;printf("%lld\n", n - ans);}return 0;
}

B - 抢课啦!

结构体排序

#include <iostream>
#include <algorithm>
using namespace std;typedef struct{int id, cnt;
}cla;
cla arr[10005];bool cmp(cla a, cla b)
{if (at != bt)return at < bt;elsereturn a.id < b.id;
}int main(void)
{int n, m, k, t;cin >> n >> m;for (int i = 1; i <= m; i++)arr[i].id = i;for (int i = 1; i <= n; i++){cin >> k;while (k--){cin >> t;arr[t]t++;}}sort(arr + 1, arr + m + 1, cmp);for (int i = 1; i <= m; i++){cout << arr[i].id << ' ' << arr[i]t << endl;}return 0;
}

C - ICPC-无限路之城

完全图的边数

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;int main(void)
{ll t, n, m;cin >> t;while (t--){cin >> n >> m;cout << n * (n - 1) / 2 - m << endl;}return 0;
}

D - 赌神

#include <iostream>
#include <algorithm>
using namespace std;int main(void)
{int n, ans;while (cin >> n){ans = 0;while (n != 1){if (n % 2 == 1)n -= 1;elsen /= 2;ans++;}cout << ans << endl;}return 0;
}

G - 卖萌型选手

这道题二分的话本人没写成
需要预先估计一下第多少项可爱度才能大于1e18
先在数组中保存好每一次的可爱度，再用upper_bound函数即可

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5e6 + 5;ll arr[N];int main(void)
{ll t, k, idx;for (ll i = 1; i <= N - 5; i++)arr[i] = arr[i - 1] + i * i;scanf("%lld", &t);while (t--){scanf("%lld", &k);idx = upper_bound(arr, arr + N - 5, k) - arr - 1;printf("%lld\n", arr[idx]);}return 0;
}

I - 曾有你的森林,あなたがいた森

这道题用到了尺取法

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;bool flag[N];
int arr[N];
int num[N], cnt;int main(void)
{int t, n, m, k;int l, r, ans;scanf("%d", &t);while (t--){scanf("%d%d%d", &n, &m, &k);for (int i = 1; i <= n; i++)scanf("%d", &arr[i]);cnt = 0;ans = INF;memset(flag, 0, sizeof flag);memset(num, 0, sizeof num);l = 1, r = 1;while (true){while (r <= n && cnt < k){if (arr[r] <= k && flag[arr[r]] == 0)cnt++;num[arr[r]]++;flag[arr[r]] = 1;r++;}if (cnt < k)break;ans = min(r - l, ans);if (num[arr[l]] == 1 && arr[l] <= k){cnt--;flag[arr[l]] = 0;}num[arr[l]]--;l++;}if (ans == INF)printf("-1\n");elseprintf("%d\n", ans);}return 0;
}

L - 鸡尾酒买罐子

因为这道题是是只要钱大于当前罐子就会买下，如果前面有一个很贵的罐子，后面全是便宜的罐子，这样会买下贵的罐子，所以不是钱越多越好。不具有单调性，所以不能二分
从1枚举到min(sum + 1, n)，一开始写成了min(sum, n)错了一次
因为罐子的价格可能会为0，所以sum+1也要枚举

#include <iostream>
#include <algorithm>
using namespace std;int a[305], sum;int main(void)
{int n, m, k;int money, cnt;cin >> n >> m >> k;for (int i = 1; i <= k; i++){cin >> a[i];sum += a[i];}for (int i = 1; i <= min(sum + 1, n); i++){money = i;cnt = 0;for (int j = 1; j <= k && money; j++){if (money >= a[j]){money -= a[j];cnt++;}}if (cnt >= m){cout << i << endl;return 0;}}cout << "poor chicken tail wine!" << endl;return 0;
}