CF1020A New Building for SIS
分类讨论 \(a,b\) 两个端点的几种情况就好了，特判 \(t_a=t_b\) 的情况。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,h,a,b,k;
void solve()
{
int ta,fa,tb,fb;
scanf("%d%d%d%d",&ta,&fa,&tb,&fb);
int ans=min({abs(fa-a)+abs(fb-b)+abs(a-b),abs(fa-a)+abs(fb-a),abs(fa-b)+abs(fb-a)+abs(a-b),abs(fa-b)+abs(fb-b)})+abs(ta-tb);
if(a<=fa&&fa<=b) ans=min(ans,abs(fb-fa)+abs(ta-tb));
if(a<=fb&&fb<=b) ans=min(ans,abs(fb-fa)+abs(ta-tb));
if(ta==tb) ans=min(ans,abs(fa-fb));
printf("%d\n",ans);
return;
}
int main()
{
scanf("%d%d%d%d%d",&n,&h,&a,&b,&k);
while(k--)
solve();
return 0;
}
CF1020B Badge
直接模拟就完了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
int n;
int p[N];
int c[N];
int solve(int s)
{
memset(c,0,sizeof(c));
for(int i=s;;i=p[i])
{
c[i]++;
if(c[i]>=2) return i;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
for(int i=1;i<=n;i++)
printf("%d ",solve(i));
return 0;
}
CF1020C Elections
枚举最后联合党选票的数量，只需要将其他大于当前枚举的选票的党搞一些掉，剩下的贪心选。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=3005;
int n,m;
vector<int>a[N];
long long solve(int u)
{
long long ans=0;
int tot=a[0].size();
vector<long long>val;
for(int i=1;i<=m;i++)
{
int j=0,k=a[i].size();
while(k>=u) ans+=a[i][j],j++,k--,tot++;
while(j<a[i].size()) val.push_back(a[i][j]),j++;
}
sort(val.begin(),val.end());
for(size_t i=0;i<val.size();i++)
{
if(tot>=u) break;
ans+=val[i],tot++;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int p,c;
scanf("%d%d",&p,&c);
if(p==1) c=0;
a[p].emplace_back(c);
}
for(int i=1;i<=m;i++)
sort(a[i].begin(),a[i].end());
long long ans=1e18;
for(int i=1;i<=n;i++)
ans=min(ans,solve(i));
printf("%lld",ans);
return 0;
}
CF1020D The hat
令 \(t_i=a_i-a_{\operatorname{next}(i)}\)，\(\operatorname{next}(i)\) 表示 \(i\) 对面的点。则 \(t_i-t_{i-1}\) 等于 \(-2\) 或 \(2\) 或 \(0\)。我们相当于要找到一个位置 \(i\) 使得 \(t_i=0\)。
如果 \(t_1=0\)，\(1\) 即为合法点。
如果 \(t_i\neq 0\)，则 \(t_i\) 与 \(t_{\operatorname{next}(i)}\) 的正负性相反，\(i\to \operatorname{next}(i)\) 中必有一个位置 \(j\) 满足 \(t_j=0\)，二分找这个位置即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
int n;
int a[N];
int query(int i)
{
if(a[i]!=-1) return a[i];
printf("? %d\n",i);
fflush(stdout);
scanf("%d",&a[i]);
return a[i];
}
void submit(int ans)
{
printf("! %d",ans);
fflush(stdout);
exit(0);
return;
}
int nxt(int i)
{
if(i>n/2) return i-n/2;
else return i+n/2;
}
int calc(int i)
{
return query(i)-query(nxt(i));
}
int check(int a,int b)
{
return (a>=0&&b>=0)||(a<0&&b<0);
}
int main()
{
scanf("%d",&n);
memset(a,-1,sizeof(a));
int l=1,r=nxt(1);
if(calc(l)==0) submit(l);
while(l<=r)
{
int mid=(l+r)/2;
if(calc(mid)==0) submit(mid);
if(!check(calc(l),calc(mid))) r=mid-1;
else l=mid+1;
}
submit(-1);
return 0;
}
CF1020E Sergey's problem
先从前往后扫一遍，每次如果这个点没有打过不能走的标记，就将这个点为加入答案，然后将这个点连出去的边都标记为不能走。
但是可以发现这个会有一种情况就是一个编号大的点连向编号小的点，我们会选到那个小的点。我们只需要再从后往前扫一遍将不合法的点剔除即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=1000005;
int n,m;
vector<int>G[N],G2[N];
bool vis[N],book[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x].emplace_back(y);
}
memset(vis,true,sizeof(vis));
for(int u=1;u<=n;u++)
if(vis[u])
{
book[u]=true;
for(int v:G[u])
vis[v]=false;
}
for(int u=n;u>=1;u--)
if(book[u])
{
for(int v:G[u])
book[v]=false;
}
int k=0;
for(int i=1;i<=n;i++)
if(book[i]) k++;
printf("%d\n",k);
for(int i=1;i<=n;i++)
if(book[i]) printf("%d ",i);
return 0;
}