The 16th Heilongjiang Provincial Collegiate Programming Contest
目录
D - Doin’ Time
题目思路
典型的石子合并问题，也就是区间dp
题目代码
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define int ll
int x;
vector<int> v;
const int mod = 1000003;
ll a[1005];
ll dp[1005][1005];
ll b[1005][1005];
signed main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%lld", &x);
a[i] = x;
}
for (int i = 1; i <= n; i++)b[i][i] = a[i];
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
b[i][j] = b[i][j - 1] * a[j]%mod;
}
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= n - i + 1; j++) {
int l = j, r = j + i-1;
for (int k = l; k <= r-1; k++) {
dp[l][r] =max(dp[l][r],dp[l][k] + dp[k + 1][r] + (long long)pow(b[l][k] - b[k + 1][r], 2));
}
}
}
cout << dp[1][n] << "\n";
}
F - Function
题目思路
质因数分解题目，注意时间复杂度，用欧式筛
题目代码
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define int ll
int p[10000005];
int ff[10000005];
int m;
int v[10000005];
void f() {
for (int i = 2; i <= 10000005; i++) {
if (!p[i]) {
v[++m] = i;
p[i] = i;
}
for (int j = 1; j <= m; j++) {
if (i * v[j] > 10000005) {
break;
}
p[i * v[j]] = v[j];
if (i % v[j] == 0)break;
}
}
}
signed main() {
int n;
cin >> n;
f();
ff[1] = 1;
ll sum = 1;
for (int i = 2; i <= n; i++) {
int t = i;
if (p[i] == i) {
ff[i] = 1;
}
else {
int cnt = 0;
ll kk = 1;
while (t % p[i]==0) {
t /= p[i];
kk *= p[i];
}
if (t == 1) {
ff[i] = p[i] * ff[kk / p[i] / p[i]];
}
else {
ff[i] = ff[kk] * i / kk;
}
}
sum += ff[i];
}
cout << sum << endl;
}
J - JOJO’s Factory
题目思路
注意删掉的边数最多不超过2*N-3，也就是说只要不是n个B都无法配对，就一定可以配对。
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=2e5+10;
const ll mod=998244353;
ll n,m;
map<ll,ll> mp,mt;
int main()
{
scanf("%lld%lld",&n,&m);
ll a=n,b=n;
for(int i=1;i<=m;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
mp[x]++;
mt[y]++;
if(mp[x]>=n)a--;
if(mt[y]>=n)b--;
//cout<<a<<" "<<b<<" "<<mp[x]<<" "<<mt[y]<<endl;
}
printf("%lld\n",min(a,b));
return 0;
}
K. Keep Eating
题目思路
题目其实一点都不难，但是没有读清题目还是wa了好多次，最多吃一半有的时候不要局限于题目中过于醒目的限制条件，每次可以只吃一口直到吃到k时再吃一半才会吃最多（秦加内帕布）
题目代码
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
signed main() {
int a, b;
cin >> a >> b;
ll sum = 0;
ll x;
for (int i = 1; i <= a; i++) {
scanf("%lld", &x);
sum += x;
}
if (sum < b)sum = 0;
else {
sum -= (b / 2);
if (b & 1) {
sum -= 1;
}
}
cout << sum << endl;
}
结语
“遇事不决，可问春风。春风不语，即随本心。”的意思是：对一件事犹豫不决，就问春风该如何做，春风给不出答案，就凭自己本心做出决断。“遇事不决可问春风，春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》，其原文是：“遇事不决，可问春风。春风不语，遵循己心”。
