最难受的事情莫过于比赛还剩20min，你锁了题，然后叉了自己。
锁题有风险，叉人需谨慎。
A. Choose Two Numbers
题意
从两个序列中各选取一个数，要求这两个数的和不属于这两个序列。
序列长度 $N\le 200$
题解
水题，$N^2$ 枚举。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
bool vis[405];
int n,m,x[105],y[105];
signed main()
{
n=read();
for (int i=1;i<=n;i++) x[i]=read(),vis[x[i]]=1;
m=read();
for (int i=1;i<=m;i++) y[i]=read(),vis[y[i]]=1;
int cnt=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if (vis[x[i]+y[j]]) continue;
printf("%d %d",x[i],y[j]);
return 0;
}
}
}B. Make Product Equal One
题意
有一个长度为 $N$ 的序列，可以修改其中的数字，每 $+1,-1$ 的代价为 $1$ 。要求修改后所有数的乘积为 $1$ ，求最小代价。
$N\le 100000$ 。
题解
显然 $1$ 和偶数个 $-1$ 乘积才为 $1$ ，所以只能改成 $1,-1$ 。
先贪心的把 $> 0$ 的改成 $1$ ，$< 0$ 的改成 $-1$ ，并记录个数。$=0$ 不论怎么改代价都是 $1$ ，同样记录个数。
如果最后有奇数个 $-1$ ，且没有 $=0$ 的数，那么就必须把一个 $-1$ 改成 $1$ ，$ans+=2$ 。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
ll n,s,ans,cnt0,cnt1,cnt2;
signed main()
{
n=read();
for (int i=1;i<=n;i++)
{
s=read();
if (s==0) cnt0++,ans++;
else if (s<0) cnt2++,ans+=-1-s;
else cnt1++,ans+=s-1;
}
if (cnt2&1 && cnt0==0) ans+=2;
cout<<ans;
return 0;
}C. Almost Equal
题意
把 $1..2N$ 的数放在一个圆环上，要求所有连续 $N$ 个数之和差值不能超过 $1$ 。询问是否有满足条件的方案，如果有还要求输出方案。
$N\le 100000$ 。
题解
找下规律，可以发现奇数可以偶数不行。
顺时针前 $N$ 个数为 $1,2N,3,2N-2,5,...,N$ 。后 $N$ 个数为前 $N$ 个的同组另一个数，即 (s[i]+1)^1)-1 。
证明？OI是工科，意会一下就行了。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
int n,s[100005];
signed main()
{
n=read();
if (n%2==0) return 0&puts("NO");
puts("YES");
int l=1,r=n<<1;
for (int i=1;i<=n;i++)
{
if (i%2==1) s[i]=l,l+=2;
else s[i]=r,r-=2;
printf("%d ",s[i]);
}
for (int i=1;i<=n;i++) printf("%d ",((s[i]+1)^1)-1);
return 0;
}D. Shortest Cycle
题意
有 $N$ 个数，如果 $A_i \ and \ A_j \neq 0$ ，则 $(i,j)$ 有一条边。求最小的环。没有环输出 -1 。
$N\le 100000 \ , \ A_i\le 10^{18}$
题解
直接连边显然是 $N^2$ ，考虑对其进行优化。
新建 $64$ 个中转点，如果 $A_i$ 的二进制的第 $k$ 位是 $1$ ，就把它和第 $k$ 个中转点相连。这样有 $N+64$ 个点，最多 $64N$ 条边。答案为最小环 $\div 2$ 。
但这样其实是有问题的，如下面的数据（我叉我自己）：
3
1 1 3三个点都连在第 $1$ 个中转点上，它们之间就可以构成环，但如果按照上述方式连边就会得到 -1 。
所以对每一个中转点记录度数 $c[k]$ ，如果 $c[k]\geq 3$ ，那么答案就是 $3$ 。
然后就可以 $\text{dfs}$ 找环了。记录深度和访问情况，如果找到环当前答案就是 $\dfrac{(deep[x]-deep[y])+1}{2}$ 。
但这样也有问题，如果遇到环套环，就可能会走冤枉路。那么从每个点出发 $\text{dfs}$ 一遍就好了。
什么？你说这是 $N^2$ 的？不，如果所有 $c[k] < 3$ ，那么最多 $128$ 个点，显然是够的。
Time limit exceeded on test 17（尴尬）
原来还有 $0$ 这个搅屎棍，把它忽略掉就行了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
struct Edge {
ll next,to;
} edge[12800005];
bool vis[100105];
ll cnt,head[100105],n,ans=1e18,pcnt,id,s[100105],deep[100105],c[100105];
inline void add(ll u,ll v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dfs(ll x,ll f,ll dep)
{
vis[x]=1;
deep[x]=dep;
for (ll i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to;
if (y==f) continue;
if (vis[y])
{
ll cur=abs(deep[y]-deep[x])+1; //因为是双向边，所以可能出现负数，取绝对值即可
if (cur==4) continue; //如果环大小为4，那么在原图中是自环
ans=min(ans,cur>>1);
}
else dfs(y,x,dep+1);
}
}
signed main()
{
n=read();
for (int i=1;i<=n;i++) s[i]=read(),pcnt+=s[i]>0;
for (ll i=1;i<=n;i++)
{
if (!s[i]) continue; //跳过0
id++;
for (ll j=63;~j;j--)
{
if (s[i]>>j&1)
{
add(id,j+pcnt+1);
add(j+pcnt+1,id); //连边
c[j]++;
}
}
}
n=pcnt;
for (int i=63;~i;i--)
{
if (c[i]>=3)
{
ans=3;
goto output;
}
}
for (ll i=1;i<=n+64;i++)
{
memset(vis,0,sizeof(vis));
memset(deep,0,sizeof(deep));
dfs(i,0,1);
}
if (ans==1e18) ans=-1;
output:
cout<<ans;
return 0;
}