每日垫底 (1/1)。为啥 T1 暴力跑 BK 跑过去了啊。
题不错，区分度很好，把我区分掉了。
挑战 NPC
原题 P6900。感觉有紫。场上想了半天计算几何，无果。
正解很奇妙。
首先这是个最大团。原题可以随机化最大团艹过去。
一个奇妙做法是枚举点对，设是 \(A,B\) 两点，那么扒出来所有和这两个点距离 \(\le AB\) 的所有点（就是 \(A,B\) 为圆心，\(AB\) 为半径的两个圆的交的所有点），跑它们的最大团即可。最大团是补图的最大独立集，那么补图就是这些点里所有距离大于 \(AB\) 的点连边。这是个二分图，因为把这个区域以 \(AB\) 为分割线，每一边内部的所有点距离都 \(\le AB\)。复杂度 \(O(n^{4.5})\)。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
int n,m,S,T;
struct gra{
int v,w,next;
}edge[1000010];
int t,head[210],head2[210],dis[210],ans[100010];
void Add(int u,int v,int w){
edge[++t].v=v;edge[t].w=w;edge[t].next=head[u];head[u]=t;
}
void add(int u,int v,int w){
Add(u,v,w);Add(v,u,0);
}
queue<int>q;
bool bfs(int st){
for(int i=1;i<=n;i++)head2[i]=head[i],dis[i]=0;
dis[st]=1;q.push(st);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].next){
if(edge[i].w&&!dis[edge[i].v]){
dis[edge[i].v]=dis[x]+1;
if(edge[i].v==T){
while(!q.empty())q.pop();
return true;
}
q.push(edge[i].v);
}
}
}
return false;
}
int dfs(int x,int flow){
if(x==T)return flow;
int sum=0;
for(int &i=head2[x];i;i=edge[i].next){
if(edge[i].w&&dis[edge[i].v]==dis[x]+1){
int ret=dfs(edge[i].v,min(flow,edge[i].w));
if(ret){
edge[i].w-=ret;edge[i^1].w+=ret;
flow-=ret;sum+=ret;
if(!flow)break;
}
else dis[edge[i].v]=-1;
}
}
return sum;
}
struct node{
long long x,y;
node operator-(const node&s)const{
return {x-s.x,y-s.y};
}
long long operator*(const node&s)const{
return x*s.y-y*s.x;
}
}a[110];
long long Dis(node a,node b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int a1[110],a2[110];
void solve(int x,int y){
int cnt=2;
long long d=Dis(a[x],a[y]);a1[0]=a2[0]=0;
t=1;for(int i=1;i<=n;i++)head[i]=0;
S=x,T=y;
for(int i=1;i<=n;i++){
if(i==x||i==y)continue;
if(Dis(a[i],a[x])>d||Dis(a[i],a[y])>d)continue;
cnt++;
if((a[y]-a[x])*(a[i]-a[x])>=0)add(x,i,1),a1[++a1[0]]=i;
else add(i,y,1),a2[++a2[0]]=i;
}
for(int i=1;i<=a1[0];i++){
for(int j=1;j<=a2[0];j++){
if(Dis(a[a1[i]],a[a2[j]])>d)add(a1[i],a2[j],1);
}
}
int sum=0;
while(bfs(S))sum+=dfs(S,0x3f3f3f3f);
int pos=ceil(sqrt(d));sum=cnt-sum;
if(pos<=m)ans[pos]=max(ans[pos],sum);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++)solve(i,j);
}
ans[0]=1;
for(int i=0;i<=m;i++)ans[i+1]=max(ans[i+1],ans[i]),printf("%d ",ans[i]);
puts("");
return 0;
}
糖果大赛
原题：ARC134E。红题。很奇妙。这辈子不会博弈论
所有数 \(\bmod 2\)，如果有 \(1\) 显然必胜。考虑剩下的。
所有数 \(\bmod 4\)，如果有 \(2\) 显然必胜。考虑剩下的。
所有数 \(\bmod 8\)，如果同时有 \(4,8\) 是必败的，否则必胜。考虑剩下的。
所有数 \(\bmod 12\)，不好说了。然而 \(200\) 内 \(12\) 的倍数只有 \(16\) 个，打张大表即可。
然后就是状压方案数，总数减掉就行了。
卡常，少取模。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int mod=998244353;
int n,ans,a[210],dp[2][1<<20];
int v[]={1,2,4,8,12,24,36,48,60,72,84,96,108,120,132,144,156,168,180,192};
int ls[]={1,2,12,48,80,144,192,352,720,2592,4192,4672,4704,4928,5760,5776,5824,5840,6240,6720,6752,8400,9424,9808,12496,12880,13328,13376,13392,13456,13504,13520,13824,13840,13888,13904,19232,33024,33408,33600,33792,33984,34512,34816,34848,35072,41552,42064,42704,46720,46736,46784,46800,49984,51488,51968,54016,54080,67088,67264,70336,74816,74832,75456,77904,99840,99856,100032,102544,103104,106560,106576,107584,108224,110672,131616,148256,149760,149792,164352,164384,180992,181024,182528,263360,263824,276096,276112,276160,276176,283200,283456,296592,297024,304784,307216,311360,315904,315968,329344,329360,332416,332432,336896,336912,339984,340608,340624,341632,341648,341696,341712,362112,362128,362192,365184,369664,369680,369744,370304,370320,370384,374400,374416,374464,374480,525376,525504,525904,526032,528976,534224,537296,557184,558672,565376,565888,565968,566864,569936,570064,570496,570880,570896,570944,570960,591424,591440,591568,593936,594048,594064,594512,594640,598720,599616,599760,602816,602832,624192,624208,626704,627280,627408,631360,631488,631504,632384,632400,635472,635584,635600,636416,636432,636480,636496,787520,787584,788048,788176,791120,791248,795344,796304,796368,799440,820288,820352,820416,820816,823824,823888,823952,824016,828048,828112,829008,832016,832080,832144,832208,833024,833040,833088,833104,853568,853584,853696,853712,856592,856656,856768,856784,860800,860816,860864,860880,861696,861712,861760,861776,861824,861840,861888,861904,864784,864848,864960,864976,865792,865808,865856,865872,886336,886352,886464,889344,889360,889408,889424,889488,889536,889552,893440,893456,893504,893520,893568,893584,893632,893648,894464,894480,894528,894544,894656,897536,897552,897600,897616,897664,897680,897728,897744,898560,898576,898624,898640};
#define add(x,y) (x+y>=mod?x+y-mod:x+y)
#define sub(x,y) (x<y?x-y+mod:x-y)
int main(){
scanf("%d",&n);
ans=1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans=1ll*ans*a[i]%mod;
dp[0][0]=1;
for(int i=1;i<=n;i++){
memset(dp[i&1],0,sizeof(dp[i&1]));
int cnt=0;
for(int x:v){
if(x>a[i])break;
for(int k=0;k<(1<<20);k++)dp[i&1][k|(1<<cnt)]=add(dp[i&1][k|(1<<cnt)],dp[(i&1)^1][k]);
cnt++;
}
}
for(int x:ls)ans=sub(ans,dp[n&1][x]);
printf("%d\n",ans);
return 0;
}
聚会
原题：JOISC2017D。不会。
标签：AB,210,省选,sum,int,add,联测,武汉,include From： https://www.cnblogs.com/gtm1514/p/17211457.html