\(\color{white}{\mathbb{燕子来时青尚在，木荫遥看杏花菲，名之以：杏红}}\)
考场发现 \(t2\) 基本上是原题，\(t3\) 的套路见过，\(t4\) 像是并查集之类的算法，\(t1\) 是个扩欧，总之感觉今天的题非常可做
先写 \(t3\) 打完二进制分组，过了大样例，然后也没测时间也没对拍开始写 \(t2\)，很快也过了大样例，然后推 \(t1\)，像是个三分，打完稍调一下也过了大样例。
发现时间还有两个半小时，觉得良心出题人前三题都给了大样例，估计不用对拍了吧，于是开始想 \(t4\)
想了一个小时复杂度大概对了，半个小时码完，再写个暴力挂上对拍
发现还有将近一个小时，开始喝水上厕所(一度以为有生之年可以AK了)
最后考完发现两题都挂了，发现 \(t1\) 有个三分的细节写错了，\(t3\) 是位运算弄错了，总共挂了 135 的分……
还是得认真检查……
A. 数列
很明显是扩欧，然后要求一组解使得 \(abs(x)+abs(y)\) 最小，这个是单峰函数，写了个三分，但是左右 \(mid\) 写错了
更简单的做法是令 \(a < b\)，那么求通解的时候 \(x\) 每次跨度大，\(y\) 跨度小，所以当 \(abs(x)\) 小的时候一定答案最小
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
int n,a,b,g,x,y,p[maxn],ans,xx,yy,ax,ay;
int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
void exgcd(int a,int b){
if(!b){
x=1;
y=0;
return ;
}
exgcd(b,a%b);
int k=y;
y=x-a/b*y;
x=k;
return ;
}
int calc(int k){
return abs(xx+k*ax)+abs(yy-k*ay);
}
int solve(int val){
if(val%g){
puts("-1");
exit(0);
}
xx=x*val/g;
yy=y*val/g;
int l=-1e9,r=1e9,lastl=0,lastr=0,cnt=0;
while(l<r){
int lmid=(r-l+1)/3+l;
int rmid=l+r-lmid;
//cout<<l<<" "<<r<<" "<<lmid<<" "<<rmid<<endl;
if(calc(lmid)<calc(rmid))r=rmid;
else l=lmid;
if(l==lastl&&r==lastr)cnt++;
else lastl=l,lastr=r,cnt=0;
if(cnt>=2)break;
}
int mn=0x3f3f3f3f3f3f3f3f;
for(int i=l-1;i<=r+1;i++){
mn=min(mn,calc(i));
}
return mn;
}
signed main(){
//freopen("array.in","r",stdin);
//cout<<gcd(12,18);
n=read();
a=read();
b=read();
g=gcd(a,b);
//cout<<g<<endl;
exgcd(a,b);
ax=b/g;
ay=a/g;
//cout<<x<<" "<<y<<endl;
for(int i=1;i<=n;i++){
p[i]=read();
}
for(int i=1;i<=n;i++){
ans+=solve(abs(p[i]));
}
cout<<ans;
return 0;
}B. 数对
类似与队长快跑，只不过这道题无序，按 \(min(a_i,b_i)\) 排序即可
C. 最小距离
二进制拆分写错+卡常挂成零分
一定注意 \((1<< pos ) \& x\) 的值不是 \(1\)！！！！
正解是记录每个点更新的源点或者次短路
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=4e5+5;
const int maxm=1e6+5;
int n,m,x,y,w,hd[maxn],cnt,dis[maxn],a[maxn],k,ans[maxn],col[maxn];
bool vis[maxn];
int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
struct Edge{
int nxt,from,to,val;
}edge[maxm];
void add(int u,int v,int w){
edge[++cnt].nxt=hd[u];
edge[cnt].to=v;
edge[cnt].val=w;
edge[cnt].from=u;
hd[u]=cnt;
return ;
}
struct Node{
int dis,id;
Node(){}
Node(int x,int y):dis(x),id(y){}
bool operator < (const Node & x)const{
return dis>x.dis;
}
};
priority_queue<Node>q;
void dij(){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
for(int i=1;i<=k;i++){
col[a[i]]=i;
q.push(Node(0,a[i]));
dis[a[i]]=0;
}
while(!q.empty()){
int u=q.top().id;
q.pop();
if(vis[u])continue;
vis[u]=true;
for(int i=hd[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val){
dis[v]=dis[u]+edge[i].val;
col[v]=col[u];
q.push(Node(dis[v],v));
}
}
}
return ;
}
signed main(){
//freopen("distance.in","r",stdin);
//freopen("my.out","w",stdout);
n=read();
m=read();
k=read();
memset(ans,0x3f,sizeof ans);
for(int i=1;i<=k;i++){
a[i]=read();
}
for(int i=1;i<=m;i++){
x=read();
y=read();
w=read();
add(x,y,w);
add(y,x,w);
}
dij();
for(int i=1;i<=cnt;i++){
if(col[edge[i].from]!=col[edge[i].to]){
ans[col[edge[i].from]]=min(ans[col[edge[i].from]],edge[i].val+dis[edge[i].from]+dis[edge[i].to]);
ans[col[edge[i].to]]=min(ans[col[edge[i].to]],edge[i].val+dis[edge[i].from]+dis[edge[i].to]);
}
}
for(int i=1;i<=k;i++){
printf("%lld ",ans[i]);
}
return 0;
}
D. 真相
这种题一看类似于图论
按照真假拆点建图后发现分成多个块，每个块的结尾都是 \(1\) 类节点
那么一种思路是枚举每个结尾点，统计所有与其相同的节点的真话总数，判断是否满足即可，这个可以预处理优化成 \(O(n)\)
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int t,n,a[maxn],val[maxn],pos[maxn],val1[maxn],tot,w[maxn],sumtot,sum1[maxn],sum2[maxn];
bool vis[maxn];
char c[5];
int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
void work(){
int op=0;
for(int i=1;i<=n;i++){
op^=a[i];
}
if(op==0)puts("consistent");
else puts("inconsistent");
return ;
}
void pre(){
for(int j=1;j<=tot;j++){
int p=pos[j];
int op=0;
while(!vis[p-1]){
p--;
if(!p)p=n;
if(vis[p])break;
op^=a[p];
val[j]+=(!op);
}
val[j]++;
p=pos[j],op=1;
while(!vis[p-1]){
p--;
if(!p)p=n;
if(vis[p])break;
op^=a[p];
val1[j]+=(!op);
//cout<<p<<" "<<a[p]<<" "<<op<<endl;
}
//cout<<val[j]<<" "<<val1[j]<<endl;
}
return ;
}
bool solve(){
for(int i=1;i<=n;i++){
sum1[w[i]]+=val[i];
sum2[w[i]]+=val1[i];
sumtot+=val1[i];
}
for(int i=1;i<=tot;i++){
int sum=sumtot-sum2[w[i]]+sum1[w[i]];
if(sum==w[i])return true;
}
int sum=0;
for(int i=1;i<=tot;i++){
sum+=val1[i];
}
for(int i=1;i<=tot;i++){
if(sum==w[i])return false;
}
return true;
}
void init(){
for(int i=1;i<=n;i++){
a[i]=vis[i]=val[i]=val1[i]=sum1[i]=w[i]=sum2[i]=0;
}
tot=sumtot=0;
return ;
}
int main(){
//freopen("shuju.in","r",stdin);
//freopen("my1.out","w",stdout);
t=read();
while(t--){
init();
n=read();
for(int i=1;i<=n;i++){
scanf("%s",c+1);
if(c[1]=='$')pos[++tot]=i,vis[i]=true,w[tot]=read();
else if(c[1]=='-')a[i]=1;
else a[i]=0;
}
if(!tot){
work();
continue;
}
pre();
if(solve())puts("consistent");
else puts("inconsistent");
}
return 0;
}
\(\color{white}{\mathbb{花褪残红青杏小，燕子来时，绿水人家绕。}}\)
