总结
签到太慢太慢太慢
记忆化搜索写炸了，1h半龟速签到。
一个裸的前缀和写好久，全队缺乏数据结构知识
一个思维倒推想不到，麻了
1004 题意
有好多条线段，alice选k条，之后bob画一条，有几个交点扣几分。alice想最大化，bob想最小化，给出线段，输出k为1到n时分数
1004 思路
k=n时，alice全选，那么bob的扣分就是n-出现次数最多的斜率出现数。之后考虑倒推，显然alice要不画当前斜率出现最多的一条边最优，所以统计线段斜率，用个优先队列倒着推就行，nlogn。
1004 代码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define online_judge
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, x, y) for (auto i = (x); i != (y + 1); ++i)
#define dep(i, x, y) for (auto i = (x); i != (y - 1); --i)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
double func(int x0, int y0, int x1, int y1) {
if (x0 == x1) return inf;
return 1.0 * (y1 - y0) / (x1 - x0);
}
unordered_map<double, int> mp;
void test_case() {
int n;
cin >> n;
mp.clear();
for (int i = 1; i <= n; ++i) {
int x0, y0, x1, y1;
cin >> x0 >> y0 >> x1 >> y1;
++mp[func(x0, y0, x1, y1)];
}
vector<int>ans;
priority_queue<int>q;
for(auto p:mp){
q.push(p.second);
}
for(int i=n;i;i--){
int t=q.top();q.pop();
ans.push_back(i-t);
q.push(t-1);
}
reverse(ans.begin(),ans.end());
for(int i=0;i<n;i++)
cout<<ans[i]<<endl;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
#ifndef online_judge
freopen("IO\\in.txt", "r", stdin);
freopen("IO\\out.txt", "w", stdout);
clock_t start, end;
start = clock();
#endif
int _;
cin >> _;
for (int i = 1; i <= _; ++i) test_case();
#ifndef online_judge
end = clock();
cout << endl
<< "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";
#endif
return 0;
}
1007 题意
n个颜色，有自己的颜色混合类型和rgb三个值，每次问lr区间颜色混合最后结果。类型为1代表覆盖，新颜色会覆盖旧颜色，2代表加和，新颜色的rgb是两个颜色的和与255取min。
1007 思路
对于lr，我们至于要找出区间内最靠右的1型位置pos，之后求一下pos到r的区间合，之后与255取min输出即可。
找出pos可以On预处理，这里用了st表，属于大材小用了。之后区间和是前缀和处理的。
1007 代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
using namespace std;
typedef long long ll;
const int maxn=400505;
const int inf=0x3f3f3f3f;
int sum[maxn][3];
int ST[maxn][20];
int arr[maxn];
int logn[maxn];
int n,m;
string s;
int ver[maxn];
int r[maxn],g[maxn],b[maxn];
inline char tran(int c){
if (c==10) return 'A';
if (c==11) return 'B';
if (c==12) return 'C';
if (c==13) return 'D';
if (c==14) return 'E';
if (c==15) return 'F';
return c+'0';
}
inline void print(int x){
if (x>255) x=255;
int u=x/16,v=x%16;
cout<<tran(u)<<tran(v);
}
inline int trans(int c){
if (c=='A') return 10;
if (c=='B') return 11;
if (c=='C') return 12;
if (c=='D') return 13;
if (c=='E') return 14;
if (c=='F') return 15;
return c-'0';
}
void preST(int len){
for(int i=1;i<=len;i++)
ST[i][0]=arr[i];
int t=logn[len]+1;
for(int j=1;j<t;j++)
for(int i=1;i<=len-(1<<j)+1;i++)
ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
int query(int l,int r){
int k=logn[r-l+1];
return max(ST[l][k],ST[r-(1<<k)+1][k]);
}
void solve(){
cin>>n>>m;
sum[0][0]=sum[0][1]=sum[0][2]=0;
for (int i=1;i<=n;i++){
cin>>ver[i];
cin>>s;
r[i]=trans(s[0])*16+trans(s[1]);
g[i]=trans(s[2])*16+trans(s[3]);
b[i]=trans(s[4])*16+trans(s[5]);
sum[i][0]=sum[i-1][0]+r[i];
sum[i][1]=sum[i-1][1]+g[i];
sum[i][2]=sum[i-1][2]+b[i];
}
for(int i=1;i<=n;i++){
if(ver[i]==1) arr[i]=i;
else arr[i]=0;
}
preST(n);
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
int p=max(query(l,r),l);
print(sum[r][0]-sum[p-1][0]);
print(sum[r][1]-sum[p-1][1]);
print(sum[r][2]-sum[p-1][2]);
cout<<endl;
}
}
signed main(){
IOS
#ifndef ONLINE_JUDGE
freopen("IO\\in.txt","r",stdin);
freopen("IO\\out.txt","w",stdout);
#endif
int tn=1;
cin>>tn;
logn[1]=0;
for(int i=2;i<maxn;i++)
logn[i]=logn[i/2]+1;
while(tn--){
solve();
}
}
1010 题意
一张图，每条边有原价和折扣价。输出使用1,2,3,4.。。条折扣边的最小生成树
1010 思路
拆边成黑白二色，变成了选择k条黑色边的最小生成树。这个刚写了博客了，是二分。现在要输出全部1-n的答案，考虑枚举所有边权预处理，之后每个去扫就行了。这里注意要提前跑一下纯黑边和纯白边的生成树，非树边直接舍弃，这个不知道是怎么证的，就这样吧…
1010 代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;
typedef long long ll;
const int maxn=400505;
const int inf=0x3f3f3f3f;
int n,m,k;
struct Edge{
int u,v,w;
}e1[maxn],e2[maxn];
int cost[maxn],need[maxn];
bool cmp(Edge a,Edge b){
return a.w<b.w;
}
int fa[maxn];
int find(int x){
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
bool unite(int x,int y){
x=find(x),y=find(y);
if(x==y) return 0;
fa[x]=y;
return 1;
}
void reduce(Edge *e){
sort(e+1,e+1+m,cmp);
for(int i=0;i<=n;i++) fa[i]=i;
int c=0;
for(int i=1;i<=m;i++){
if(unite(e[i].u,e[i].v)){
e[++c]=e[i];
}
}
}
int out(int x){
for(int i=0;i<=2000;i++){
if(need[i]<=x)
return cost[i]-x*(i-1000);
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e1[i].u>>e1[i].v>>e1[i].w>>e2[i].w;
e2[i].u=e1[i].u,e2[i].v=e1[i].v;
}
reduce(e1),reduce(e2);
for(int i=-1000;i<=1000;i++){
for(int j=1;j<=n;j++) fa[j]=j;
int A=1,B=1,sum=0,cnt=0;
while(A<n&&B<n){
if(e1[A].w<=e2[B].w+i){
if(unite(e1[A].u,e1[A].v))
sum+=e1[A].w;
A++;
}
else{
if(unite(e2[B].u,e2[B].v))
sum+=e2[B].w+i,cnt++;
B++;
}
}
while(A<n){
if(unite(e1[A].u,e1[A].v))
sum+=e1[A].w;
A++;
}
while(B<n){
if(unite(e2[B].u,e2[B].v))
sum+=e2[B].w+i,cnt++;
B++;
}
need[i+1000]=cnt;
cost[i+1000]=sum;
}
for(int i=0;i<n;i++)
cout<<out(i)<<endl;
}
signed main(){
IOS
#ifndef ONLINE_JUDGE
freopen("IO\\in.txt","r",stdin);
freopen("IO\\out1.txt","w",stdout);
#endif
int tn=1;
cin>>tn;
while(tn--){
solve();
}
}
1011 题意
给出n，k求1-n的线段树，在节点比k小时不再分裂，共要开多少个点
1011 思路
记忆化搜索
1011 代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
using namespace std;
typedef long long ll;
const int maxn=400505;
const int inf=0x3f3f3f3f;
int n,m,k;
map<int,int>mp;
int fun(int len){
if(len<=k) return 1;
if(mp[len]) return mp[len];
int rec=0;
if(len&1)
rec+=fun(len/2)+fun(len/2+1);
else
rec+=2*fun(len/2);
return mp[len]=rec+1;
}
void solve(){
cin>>n>>k;
mp.clear();
cout<<fun(n)<<endl;
}
signed main(){
IOS
#ifndef ONLINE_JUDGE
freopen("IO\\in.txt","r",stdin);
freopen("IO\\out.txt","w",stdout);
#endif
int tn=1;
cin>>tn;
while(tn--){
solve();
}
}
1009 题意
n*n方格左上走到右下，每个格子都可获得新钻石并永久提升所有钻石价格，终点卖出所有宝石，数据随机，问最大收益
E 思路
我们用dpijk代表i，j位置拿了k个宝石的最大收益。显然如果ij确定后，我们可以比较两个状态的优劣。如果状态a的k和收益全大于状态b的k和收益，那么a一定优于b。所以我们开一个三维数组dp，每个dpij对应一个存pair<int,int>的vector，就是维护一个位置的不同k和收益的列表。我们考虑合并，只有ij都大于1时涉及合并，合并时我们保存有效状态即可。因为是随机数据，所以状态不会特别多。
E 代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;
typedef long long ll;
const int maxn=105;
const int inf=0x3f3f3f3f;
int n,m,k;
int mp1[maxn][maxn],mp2[maxn][maxn];
vector<pair<int,int>>dp[maxn][maxn];
pair<int,int>buf[2000005];
int cnt;
void inse(pair<int,int> p){
while(cnt&&buf[cnt].second<=p.second) cnt--;
buf[++cnt]=p;
}
void unite(vector<pair<int,int>> &to,const vector<pair<int,int>> &f1,const vector<pair<int,int>>&f2){
int s1=f1.size(),s2=f2.size();
int p1=0,p2=0;
cnt=0;
while(p1<s1&&p2<s2){
if(f1[p1].first<f2[p2].first){
inse(f1[p1++]);
}
else{
inse(f2[p2++]);
}
}
while(p1<s1){
inse(f1[p1++]);
}
while(p2<s2){
inse(f2[p2++]);
}
for(int i=1;i<=cnt;i++)
to.emplace_back(buf[i]);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&mp1[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&mp2[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j].clear();
dp[1][1].resize(1);
dp[1][1][0]={mp1[1][1],mp2[1][1]};
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==1&&j==1) continue;
if(i==1){
dp[i][j]=dp[i][j-1];
}
else if(j==1){
dp[i][j]=dp[i-1][j];
}
else{
unite(dp[i][j],dp[i-1][j],dp[i][j-1]);
}
for(auto &p:dp[i][j]){
p.first+=mp1[i][j];
p.second+=mp2[i][j];
}
}
}
ll ans=0;
for(auto p:dp[n][n])
ans=max(ans,1ll*p.first*p.second);
printf("%lld\n",ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("IO\\in.txt","r",stdin);
freopen("IO\\out.txt","w",stdout);
#endif
int tn=1;
scanf("%d",&tn);
while(tn--){
solve();
}
}
未完待续
|