天才ACM
倍增。以上一个划分的终点为起点,倍增求这个划分的终点。
const int N=5e5+10;
int n,m,T,ans;
int a[N],t[N];
#define f(x) ((x)*(x))
int get(int l,int r)
{
int k=0;
fo(i,l,r-1) t[k++]=a[i];
sort(t,t+k);
int sum=0;
fo(i,0,min(m,k)-1) sum+=f(t[i]-t[k-1]),k--;
return sum;
}
void solve()
{
n=R,m=R,T=R;
fo(i,0,n-1) a[i]=R;
int ans=0,sta=0,ed=0;
while(sta<n)
{
int len=1;
while(len)
{
if(ed+len<=n&&get(sta,ed+len)<=T) ed+=len,len<<=1;
else len>>=1;
}
sta=ed,ans++;
}
write(ans),puts("");
}
贪心
股票买卖 II
每天只能买一股,所以答案为:
$$\sum_{i=2}^{n}\max(0,a_i-a_{i-1})$$
const int N=1e5+10;
int n;
int a[N];
void main(){
n=R;
fo(i,1,n) a[i]=R;
int ans=0;
fo(i,2,n) ans+=max(0ll,a[i]-a[i-1]);
write(ans);
}
防晒
-
将所有奶牛按照 minSPF 从大到小的顺序排序,然后依次考虑每头奶牛
-
对于每头奶牛,扫描当前所有能用的防晒霜,选择 SPF 值最大的防晒霜来用
const int N=2510;
int n,m;
pair<int,int> a[N];
map<int,int> ma;
void main(){
n=R,m=R;
fo(i,0,n-1) a[i].first=R,a[i].second=R;
fo(i,1,m)
{
int x=R,y=R;
ma[x]+=y;
}
sort(a,a+n);
int res=0;
ma[0]=ma[1001]=n;
rep(i,n-1,0)
{
auto tt=ma.upper_bound(a[i].second);tt--;
if(tt->first>=a[i].first)
{
res++;
if(--tt->second==0) ma.erase(tt);
}
}
write(res),puts("");
}
畜栏预定
-
将所有牛按开始吃草的时间排序
-
用小根堆维护当前所有畜栏的最后一头牛的吃草结束时间
-
如果当前的牛可以安排在堆顶的畜栏中,则将其安排进去,否则就新建一个畜栏
const int N=5e5+10;
int n;
pair<pair<int,int>,int> a[N];
priority_queue<pair<int,int> > q;
int f[N];
void main(){
n=R;
fo(i,1,n) a[i].first.first=R,a[i].first.second=R,a[i].second=i;
sort(a+1,a+n+1);
f[a[1].second]=1;
q.push({-a[1].first.second,a[1].second});
int cnt=1;
fo(i,2,n)
{
if(a[i].first.first>-q.top().first) f[a[i].second]=f[q.top().second],q.pop();
else f[a[i].second]=++cnt;
q.push({-a[i].first.second,a[i].second});
}
write(cnt),puts("");
fo(i,1,n) write(f[i]),puts("");
}
国王游戏
exchange argument。
推式子可以发现可以按照 $A_iB_i \leq A_{i+1}B_{i+1}$。
n=int(input())
king_left,tmp=map(int,input().split())
A=[]
for _ in range(n):
a,b=map(int,input().split())
A.append((a*b,a,b))
A.sort()
ans=0
m=king_left
for i in range(n):
ans=max(ans,m//A[i][2])
m*=A[i][1]
print(ans)
给树染色
推一波 exchange argument 可以发现选择到根的平均值最大的一个点总是更好的。
因此不断合并非根节点,即可。
0x00总结与练习
飞行员兄弟
注意到一个点被操作两次相当于没操作,因此每个点最多只被操作一次。
直接爆搜,枚举每个点是否被操作。
const int N=5;
char g[N][N],backup[N][N];
inline int get(int x,int y)
{
return x*4+y;
}
inline void turn(int x,int y)
{
fo(i,0,3)
{
g[x][i]='+'+'-'-g[x][i];
g[i][y]='+'+'-'-g[i][y];
}
g[x][y]='+'+'-'-g[x][y];
}
inline bool check()
{
bool flag=1;
fo(i,0,3) fo(j,0,3) if(g[i][j]!='-') flag=0;
return flag;
}
void main(){
fo(i,0,3) fo(j,0,3) cin>>g[i][j];
vector<pair<int,int> > ans;
fo(st,0,65535)
{
vector<pair<int,int> > tmp;
memcpy(backup,g,sizeof g);
fo(i,0,3) fo(j,0,3) if(st>>get(i,j)&1) tmp.pb({i,j}),turn(i,j);
if(check()&&(ans.empty()||ans.size()>tmp.size())) ans=tmp;
memcpy(g,backup,sizeof g);
}
write(ans.size()),puts("");
for(auto i:ans) write(i.first+1),pc(' '),write(i.second+1),puts("");
}
占卜DIY
考虑双端队列来模拟整个过程。
int get(char c)
{
if(c=='A') return 1;
else if(c>='2'&&c<='9') return c-'0';
else if(c=='0') return 10;
else if(c=='J') return 11;
else if(c=='Q') return 12;
else return 13;
}
deque<pair<int,bool> > q[15];
int cnt[15];
void main(){
fo(i,1,13) fo(j,1,4)
{
char c;
cin>>c;
q[i].pb({get(c),0});
}
fo(i,1,4)
{
int x=q[13].front().first;
cnt[x]++,q[13].pop_front();
while(x<13)
{
int tt=q[x].back().first;q[x].pop_back();
x=tt;
if(x!=13) q[x].push_front({x,1});
else break;
}
}
fo(i,1,12) while(!q[i].empty())
{
if(q[i].front().second) cnt[q[i].front().first]++;
q[i].pop_front();
}
int ans=0;
fo(i,1,12) if(cnt[i]==4) ans++;
write(ans);
}
分形
考虑递归处理。
将区域平均分为 9 块,则 1,3,5,7,9 这五块需要递归处理。
const int N=3010;
int n;
bool g[N][N];
void dfs(int len,int x,int y)
{
if(len==1) g[x][y]=1;
else
{
dfs(len/3,x,y);
dfs(len/3,x,y+len/3*2);
dfs(len/3,x+len/3,y+len/3);
dfs(len/3,x+len/3*2,y);
dfs(len/3,x+len/3*2,y+len/3*2);
}
}
void main(){
while(cin>>n,n!=-1)
{
int len=1;
fo(i,1,n-1) len*=3;
dfs(len,0,0);
fo(i,0,len-1)
{
fo(j,0,len-1)
if(g[i][j]) pc('x');
else pc('.');
puts("");
}
puts("-");
}
}
袭击
平面最近点对。
我们充分发扬人类智慧:
将所有点全部绕原点旋转同一个角度,然后按 $x$ 坐标排序
根据数学直觉,在随机旋转后,答案中的两个点在数组中肯定不会离得太远
所以我们只取每个点向后的 $5$ 个点来计算答案
这样速度快得飞起,在 $n=1000000$ 时都可以在 1 s 内卡过
当然,这是错的。
所以我们。
我们充分发扬人类智慧:
将所有点全部绕原点旋转同一个角度,然后按 $x \times y$ 排序。
根据数学直觉,在随机旋转后,答案中的两个点在数组中肯定不会离得太远。
所以我们只取每个点向前的 $50$ 个点来计算答案。
这样速度快得飞起,在 $n=400000$ 时都可以在 124ms 内卡过。
防线
前缀和的奇偶性具有单调性。
因此二分这个位置。
const int N=2e5+10;
int n;
struct Node{
int s,e,d;
}a[N];
int get_sum(int x)
{
int res=0;
fo(i,1,n) if(a[i].s<=x) res+=(min(a[i].e,x)-a[i].s)/a[i].d+1;
return res;
}
bool check(int l,int r)
{
return (get_sum(r)-get_sum(l-1))&1;
}
void solve()
{
n=R;
int maxx=-2e9,minx=2e9;
fo(i,1,n)
{
a[i].s=R,a[i].e=R,a[i].d=R;
minx=min(minx,a[i].s);
maxx=max(maxx,a[i].e);
}
if(!(get_sum(maxx)&1)) return void(puts("There's no weakness."));
else
{
int l=minx,r=maxx;
while(l<=r)
{
int mid=l+r>>1;
if(check(l,mid)) r=mid-1;
else l=mid+1;
}
write(l),pc(' '),write(get_sum(l)-get_sum(l-1)),puts("");
}
}
void main(){
MT solve();
}
赶牛入圈
考虑离散化所有坐标。
二分答案,问题转化为判定边长小于等于 $mid$ 的正方形是否有可能权值和至少为 $C$。
但是离散化坐标后,会导致 $i$ 与 $i+1$ 之前相差并不是 $1$。
所以我们在这里根据“真实坐标”二分离散化后的坐标。
糖果传递
环形均分纸牌问题。
可见 七夕祭 题解。
士兵
不妨设最终士兵 $x$ 坐标相同,$y$ 坐标不影响最终答案。
对于 $x$ 坐标写一个货仓选址即可。
最终士兵 $y$ 坐标相同类似。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int x[N],y[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d%d",&x[i],&y[i]);
sort(x+1,x+n+1),sort(y+1,y+n+1);
int t1=x[n+1>>1],t2=y[n+1>>1],ans=0;
for (int i = 1; i <= n; i ++ ) ans+=abs(y[i]-t2);
for (int i = 1; i <= n; i ++ ) x[i]-=i-1;
sort(x+1,x+n+1);
t1=x[n+1>>1];
for (int i = 1; i <= n; i ++ ) ans+=abs(t1-x[i]);
cout << ans;
}
古早代码,空格混乱。
数的进制转换
高精除低精。
不用真的用高精,直接模拟即可。
耍杂技的牛
exchange argument。
推式子可以发现按照 $W+S$ 排序最好。
最大的和
暴力枚举所有的子矩阵,然后二维前缀和优化求和。
任务
比较讨厌这种解法基于特殊的数据范围的题目的。
$x$ 绝对优先于 $y$。
所以当做类似字典序来做即可。