P1314 聪明的质检员
来翻历届真题，发现这道题还没过。
首先瞪眼可知 \(y\) 具有单调性，所以想到二分。
先不考虑 \(check\) 函数，把过程写了。
这道题和常规二分不同，因为要考虑绝对值，所以需要对 \(mid\) 分正负两种情况考虑。
然后在纸上画了画，基本定型以后开始写。写了 15min 以后发现挂了，动态查错 20min 发现我 \(l\) 赋值成了 \(ch(mid)\)，人才啊。
对于 \(check\) 函数的话我想到了教主的魔法，但是看了看数据范围好像只有 70。于是想到每次要查询的数是唯一的，所以完全可以离线以后 \(\mathcal{O}(n)\) 预处理前缀和。
然后就过了。
点击查看代码
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tr;//从小到大
// int findnum(int k){auto it=tr.find_by_order(k-1);return ((it!=tr.end())?(*it):1e9+7);}//查元素
// int findrank(int x){return tr.order_of_key(x)+1;}//查排名
// static char buf[100000],*pa=buf,*pd=buf;
// #define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
const int maxn=3e6;
const int mod=998244353;
const int inf=1e9+7;
int n,m,s;
struct no
{
int w,v;
}a[maxn];
struct Ask
{
int l,r;
}q[maxn];
int sum1[maxn],sum2[maxn];
int ch(int x)
{
for(int i=1;i<=n;i++)
{
if(a[i].w>=x)sum1[i]=sum1[i-1]+1,sum2[i]=sum2[i-1]+a[i].v;
else sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];
}
int ans=0;
for(int i=1;i<=m;i++)
{
int l=q[i].l,r=q[i].r;
ans=(ans+(sum2[r]-sum2[l-1])*(sum1[r]-sum1[l-1]));
}
return ans;
}
signed main()
{
#ifdef Lydic
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
cin>>n>>m>>s;
for(int i=1;i<=n;i++)a[i]={read(),read()};
for(int i=1;i<=m;i++)q[i]={read(),read()};
int l=0,r=2e6,mid;
int ans=inf;
// for(int i=1;i<=10000;i++)ans=min(ans,abs(ch(i)-s));
// cout<<ans<<endl;
// return 0;
while(l<r)
{
mid=(l+r)>>1;
int del=ch(mid)-s;
if(del==0)break;
if(del>0)
{
int pre=ch(mid-1)-s,nxt=ch(mid+1)-s;
if(pre==0){mid=pre;break;}
if(nxt==0){mid=nxt;break;}
if(pre>0&&nxt>0){l=mid+1;continue;}
if(pre>0&&nxt<0){mid=(-nxt>del?mid:mid+1);break;}
}
else if(del<0)
{
int pre=ch(mid-1)-s,nxt=ch(mid+1)-s;
if(pre==0){mid=pre;break;}
if(nxt==0){mid=nxt;break;}
if(pre<0&&nxt<0){r=mid-1;continue;}
if(pre>0&&nxt<0){mid=(pre>-del?mid:mid-1);break;}
}
// cout<<l<<' '<<r<<endl;
}
cout<<abs(ch(mid)-s);
return 0;
}
P2129 L 国的战斗续之多路出击
很水的绿题。
模拟的话会超时。
然后想到一句著名的话“如果大山不能走向穆罕默德，那么穆罕默德可以走向大山。”
于是每次操作直接平移坐标系即可。
点击查看代码
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tr;//从小到大
// int findnum(int k){auto it=tr.find_by_order(k-1);return ((it!=tr.end())?(*it):1e9+7);}//查元素
// int findrank(int x){return tr.order_of_key(x)+1;}//查排名
// static char buf[100000],*pa=buf,*pd=buf;
// #define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
const int maxn=6e5;
const int mod=998244353;
const int inf=1e9+7;
struct no
{
int x,y;
}t[maxn];
int a[maxn],b[maxn];
int n,m;
char c[maxn];
int sx=1,sy=1,tx,ty;
signed main()
{
#ifdef Lydic
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
cin>>n>>m;
for(int i=1;i<=n;i++)t[i]={read(),read()};
for(int i=1;i<=m;i++)
{
cin>>c[i];
if(c[i]=='m'){a[i]=read();b[i]=read();}
}
for(int i=m;i>=1;i--)
{
if(c[i]=='y')sy*=-1,ty*=-1;
else if(c[i]=='x')sx*=-1,tx*=-1;
else if(c[i]=='m')tx+=a[i],ty+=b[i];
}
for(int i=1;i<=n;i++)printf("%lld %lld\n",t[i].x*sx+tx,t[i].y*sy+ty);
return 0;
}
P2212 [USACO14MAR] Watering the Fields S
按照题意建图以后跑 MST，然后一遍过了。
P10460 防线
第一眼看题上说 ＜10^8 以为能暴力。
很有用的思想。
根据题意数列中只有一个奇数。我们可以根据只有一个奇数的数列和为奇数这个性质来判断这个数字是否在某个数列中。
于是可以用二分查找实现这个过程。
那么对于 \(check\) 函数，我们现在需要实现查找数列和的功能。
有一个小学公式： \(项数=\frac{末项-首项}{公差}+1\)，然后对于每个等差数列都做一次即可。
一遍过！
点击查看代码
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tr;//从小到大
// int findnum(int k){auto it=tr.find_by_order(k-1);return ((it!=tr.end())?(*it):1e9+7);}//查元素
// int findrank(int x){return tr.order_of_key(x)+1;}//查排名
// static char buf[100000],*pa=buf,*pd=buf;
// #define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
return w*s;
}
const int maxn=2e6;
const int mod=998244353;
const int inf=1e9+7;
int T;
int n;
struct no
{
int s,e,d;
}a[maxn];
int l,r;
int sum(int x)
{
int num=0;
for(int i=1;i<=n;i++)
{
if(a[i].s>x)continue;
num+=(min(x,a[i].e)-a[i].s)/a[i].d+1;
}
return num;
}
bool ch(int x,int y)
{
return ((sum(y)-sum(x-1))&1);
}
void Main()
{
n=read();
for(int i=1;i<=n;i++)a[i]={read(),read(),read()},l=min(l,a[i].s),r=max(r,a[i].e);
if(!ch(l,r))return puts("There's no weakness."),void();int ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(ch(l,mid))r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans<<' '<<sum(ans)-sum(ans-1)<<endl;
}
signed main()
{
#ifdef Lydic
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
T=read();
while(T--)Main();
return 0;
}