开篇碎碎念
下午下课之后没事儿干vp了一手，趁着补完题还有些印象，写一手总结
赛时犯困（开始找理由）+ 又没吃到肯德基老爷爷的蛋挞（这都要扯？）开了三题，赛后补了D和E
A.Full moon
- 题意：总共有n天，第m天开始，每p天看到一次满月，问总共能看到多少次满月
- WA一发：忘记统计两端都能看到满月的情况
B.Overlapping sheets
- 题意：给定n和n个矩形，问总覆盖面积
- 思路：对于n个矩形，分别标记覆盖了哪些格子，然后统计被覆盖格子的数目
- WA四发：第一发是读假以为是未被覆盖的格子数目，第二发CE，第三发发现数据范围是0~n，所以遍历应该从下标0开始。最关键的是第四发的修改因为单位为1的格子两个顶点横跨1和2，但是只覆盖了一个格子，所以在模拟填充这个过程的时候应该是一开一闭区间！
- code：
#include<bits/stdc++.h>
using namespace std;
int ans[105][105];
int main(){
int n;
cin>>n;
int a,b,c,d;
while(n--){
cin>>a>>b>>c>>d;
for(int i=a;i<b;i++){
for(int j=c;j<d;j++){
ans[i][j]=1;
}
}
}
int tot=0;
for(int i=0;i<=100;i++){
for(int j=0;j<=100;j++){
tot+=ans[i][j];
}
}
cout<<tot<<endl;
}
C.Blue Spring
- 题意：郊游每天价格不一样，每d天可以选择一组价格为p的套票，套票可以有富裕，问最低价格花费
- 思路：考虑贪心，优先比套票平均价格贵的天数选择套票，如果天数非整套，那么取少半张套票和套票有富裕两种情况的最小值。
- wa一发：天数没有初始化
D.General Weighted Max Matching
- 题意：给你一个加权无向完整图，在以下条件下选择一定数量的边时，请找出所选边的最大可能总重量。所选边的端点是成对不同的。
- 思路：暴搜，状压；第i位为1时表示i已经链接。
- code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=20;
int a[MAXN][MAXN];
int dp[1<<MAXN];
int n;
int dfs(int x){
if(dp[x]!=-1){
return dp[x];
}
int ans=0,pre;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if((x>>i)&1 && (x>>j)&1){
pre=x-(1<<i)-(1<<j);
ans=max(ans,dfs(pre)+a[i][j]);
}
}
}
return dp[x]=ans;
}
signed main(){
cin>>n;
memset(dp,-1,sizeof dp);
dp[0]=0;
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
cin>>a[i][j];
a[j][i]=a[i][j];
}
}
int ans=0;
for(int i=2;i<(1<<(n+1));i++){
ans=max(ans,dfs(i));
}
cout<<ans<<endl;
return 0;
}
E.Sandwiches
注意贡献的计算！本质是讨论中间位置