678C Joty and Chocolate
传送门
镜像
1600 数论
题意：n块瓷砖从1~n编号，Joty可以将其中编号为a的倍数的瓷砖涂成红色，编号为b的倍数的瓷砖涂成蓝色，每涂一块红色的瓷砖可以得到p块巧克力，而蓝色的瓷砖则提供q块巧克力，最大化Joty能够得到的巧克力数。
水题~，假设x块编号是a的倍数，y块编号是b的倍数，z块编号是a和b最小公倍数的倍数，当p>q的情况下，则x+z块涂成红色，y-z块涂成蓝色，其他情况同理。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll n,a,b,p,q;
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);}
int main()
{
IOS
cin>>n>>a>>b>>p>>q;
ll m=a*b/gcd(a,b);
m=n/m;
a=n/a-m;
b=n/b-m;
ll ans;
if(p>=q)ans=(a+m)*p+b*q;
else ans=(b+m)*q+a*p;
cout<<ans;
return 0;
}
527C Glass Carving
传送门
镜像
1800 数据结构
题意：一个长h宽w的玻璃砖，每次垂直一条边切割，问每次切割后的最大面积
开两个set和两个multiset就可以解出来了，两个set分别记录x轴和y轴上面的切割点（初始就分别扔进去0,w和0,h），multiset则记录x轴或y轴上切割产生的线段，对于每次切割后，找出当前切割点两端最近的点，然后在multiset里把这段的长度erase掉，把新生成的两段插进去，最后输出两个multiset里最大值的乘积即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll n,w,h;
set<ll> x,y;
multiset<ll> a,b;
int main()
{
IOS
cin>>w>>h>>n;
y.insert(h);y.insert(0);
x.insert(w);x.insert(0);
a.insert(h);
b.insert(w);
while(n--){
char s;
ll l;
cin>>s>>l;
if(s=='H'){
auto i=y.lower_bound(l);
if(*i>l)i--;
auto j=y.upper_bound(l);
ll tmp=*i-*j;
auto m=a.lower_bound(*j-*i);
a.erase(m);
a.insert(l-*i);
a.insert(*j-l);
y.insert(l);
}else{
auto i=x.lower_bound(l);
if(*i>l)i--;
auto j=x.upper_bound(l);
ll tmp=*i-*j;
auto m=b.lower_bound(*j-*i);
b.erase(m);
b.insert(l-*i);
b.insert(*j-l);
x.insert(l);
}
auto p=a.end(),q=b.end();
q--;
p--;
cout<<(*p)*(*q)<<endl;
}
return 0;
}
小姐姐的平衡树做法：
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> x,y;
tree<pair<int,int>,null_type,greater<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> xx,yy;
cc_hash_table<int,int> hx,hy;
int w,h,n;
int main()
{
ios::sync_with_stdio(false);
cin>>w>>h>>n;
x.insert(0);
x.insert(w);
y.insert(0);
y.insert(h);
xx.insert(make_pair(w,++hx[w]));
yy.insert(make_pair(h,++hy[h]));
for(int i=0;i<n;i++)
{
char c;
int num;
cin>>c>>num;
if(c=='V')
{
int rank=x.order_of_key(num);
int pre=*x.find_by_order(rank-1);
int nxt=*x.find_by_order(rank);
xx.erase(make_pair(nxt-pre,hx[nxt-pre]--));
xx.insert(make_pair(num-pre,++hx[num-pre]));
xx.insert(make_pair(nxt-num,++hx[nxt-num]));
x.insert(num);
}
else if(c=='H')
{
int rank=y.order_of_key(num);
int pre=*y.find_by_order(rank-1);
int nxt=*y.find_by_order(rank);
yy.erase(make_pair(nxt-pre,hy[nxt-pre]--));
yy.insert(make_pair(num-pre,++hy[num-pre]));
yy.insert(make_pair(nxt-num,++hy[nxt-num]));
y.insert(num);
}
cout<<(ll)xx.find_by_order(0)->first*(ll)yy.find_by_order(0)->first<<endl;
}
return 0;
}
1012C Hills
传送门
镜像
2000 dp
题意：一共n座山，每花费1h可以使一座山降低1的高度，最少花费多少时间可以使存在k座山的高度严格大于两侧的山的高度。输出k从1~的结果。
一开始想的做法是dp[i][j][0]代表前i个有j个满足，并且最后一个不取，dp[i][j][1]代表前i个有j个满足，并且最后一个取，但是状态转移尬住了，因为还要考虑倒数第二个的状态，那开三维就好了，dp[i][j][0]代表前i个有j个满足，并且最后两个都不取，dp[i][j][2]代表前i个有j个满足，并且取最后一个，dp[i][j][1]代表前i个有j个满足，并且取倒数第二个。
那么状态转移方程就很好推了：
dp[i][j][1]=dp[i-1][j][2]+max(0,a[i]-a[i-1]+1)
dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1])
dp[i][j][2]=min(dp[i-1][j-1][0]+max(0,a[i-1]-a[i]+1),dp[i-1][j-1][1]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1))
然后就是初始化，不确定的和非法状态存为极大值，显然dp[1][1][2]=0,并且dp[i][0][0]=0（1<=i<=n）从2开始转移就可以A了
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 5005
int n,a[maxn],dp[maxn][maxn][3];
int main()
{
IOS
cin>>n;
for (int i = 1; i <=n ; ++i) {
cin>>a[i];
for (int j = 0; j <=n ; ++j) {
for (int k = 0; k <=2 ; ++k) {
dp[i][j][k]=2146870000;
}
}
dp[i][0][0]=0;
}
dp[1][1][2]=0;
for (int i = 2; i <=n ; ++i) {
for (int j = 1; j <=(i+1)/2 ; ++j) {
dp[i][j][2]=min(dp[i-1][j-1][0]+max(0,a[i-1]-a[i]+1),dp[i-1][j-1][1]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1));
dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]);
dp[i][j][1]=dp[i-1][j][2]+max(0,a[i]-a[i-1]+1);
}
}
for (int k = 1; k <=(n+1)/2 ; ++k) {
cout<<min(dp[n][k][2],min(dp[n][k][0],dp[n][k][1]))<<" ";
}
return 0;
}