Preface
这篇已经鸽了好久的说，AGC037都打完了才回来补所以题目可能都记不大清楚了，如有错误请指正
这场感觉难度远高于上一场，从D开始就不会了，E没写（看了题解都不会写），F就是抄曲明姐姐的
我还是太弱了
A - Triangle
刚开始想了一堆很SB的做法，后来才想到用叉积来解决
考虑构造向量((a,b),(c,d))，同时定下一个点在原点处，此时的三角形面积就是(ad-bc)
可以考虑像CXRdalao一样取一个底数(10^9)构造，也可以像我一样先随便搞出一个(ad)比(S)略大一些，然后暴枚一下(bc)即可
#include<cstdio>
#include<cmath>
#define RI register int
using namespace std;
const int LIM=1e9;
long long s; int a,b,c,d;
int main()
{
scanf("%lld",&s); a=d=(int)sqrt(s);
while (1LL*a*d<s) if (a<d) ++a; else ++d;
long long left=1LL*a*d-s; for (RI i=1;1LL*i*i<=left;++i)
if (left%i==0&&i<=LIM&&left/i<=LIM) { b=i; c=left/i; break; }
return printf("0 0 %d %d %d %d",a,b,c,d),0;
}
B - Do Not Duplicate
题意可能比较复杂。。。
稍微理解并画个图就会发现这种操作是有循环节的，然后画个图就知道循环节长度不会超过(n)
模拟找出循环节然后取个膜再模拟一遍233
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=400005;
int n,a[N],nxt[N],lst[N],pos,cur,ans[N],cnt; long long k;
int main()
{
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
RI i; for (scanf("%d%lld",&n,&k),i=1;i<=n;++i)
scanf("%d",&a[i]),a[n+i]=a[i];
for (i=(n<<1);i>n;--i) lst[a[i]]=i-n;
for (i=n;i;--i) nxt[i]=lst[a[i]],lst[a[i]]=i;
//for (i=1;i<=n;++i) printf("%d ",nxt[i]);
for (pos=cur=1,i=1;i<=n;++i)
{
int pxt=nxt[pos]; if (pxt<=pos) ++cur;
pos=pxt+1; if (pos==1) { --cur; break; }
}
for (pos=1,k%=cur,cur=0;;)
{
int pxt=nxt[pos]; if (pxt<=pos) ++cur;
if (cur==k) break; pos=pxt+1;
}
for (;;)
{
int pxt=nxt[pos]; if (pxt<=pos) ans[++cnt]=a[pos++];
else pos=pxt+1; if (pos>n) break;
}
for (i=1;i<=cnt;++i) printf("%d ",ans[i]);
return 0;
}
C - GP 2
挺妙的一题，和陈指导聊天的时候突然就出来了，以下是我们聊天的过程：
CXR：这种题目肯定就是把那个操作转化成一个好统计一点的操作。
我：说的太好了，您太稳了。
CXR：所以我们考虑按等于(1)的数的个数讨论。
我：这显然数不清楚啊，限定的范围太小了。
CXR：那么我们按加了(1)的数的个数讨论。
我：这TM更加复杂了，我TM直接按多少个奇数讨论，全不全面？
（一阵沉默之后我们发现按奇数讨论十分有道理，然后就出来了233）
我们根据上面的讨论很容易发现只要满足两个性质即可：
- (max(a_i)le 2m)
- (sum (a_imod 2)le m)
所以我们只需要枚举奇数的个数，然后考虑剩下的都可以随便分。运用以下隔板法就可以算出满足2的序列个数
然后我们减去不满足1的序列个数即可，具体的，从(2m+1)到(3m)枚举最大值（最大值显然只有一个），然后再运用隔板法得出分配方案即可
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=3000005,mod=998244353;
int n,m,fact[N],inv[N],ans,tp;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,CI y)
{
if ((x-=y)<0) x+=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline int C(CI n,CI m)
{
if (n<m) return 0; return 1LL*fact[n]*inv[m]%mod*inv[n-m]%mod;
}
inline void init(CI n)
{
RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
for (inv[n]=quick_pow(fact[n]),i=n-1;~i;--i) inv[i]=1LL*inv[i+1]*(i+1)%mod;
}
int main()
{
RI i; scanf("%d%d",&n,&m); init(n+3*m);
for (i=0;i<=m;++i) if (!((3*m-i)&1))
tp=(3*m-i)/2,inc(ans,1LL*C(n,i)*C(tp+n-1,n-1)%mod);
for (i=2*m+1;i<=3*m;++i) dec(ans,1LL*n*C(3*m-i+n-2,n-2)%mod);
return printf("%d",ans),0;
}
D - Negative Cycle
思路十分巧妙的一题（以下下标从(1)开始标号）
首先我们考虑这张图没有负环，那么就意味着我们可以跑最短路，它满足以下基本条件：
记(d_i)为(1 o i)的最短路，则对于((x,y)in E)，有(d_x+w(x,y)ge dis_y)
然后我们发现所有的(0)边都不能删，因此(d_ige d_{i+1})
然后后面的我就想不出了，ORZ曲明姐姐
我们定义一个(q_i=d_i-d_{i+1})，则有(q_ige 0)，并且(q_iin[0,1])
那么如果有一条长度为(1)的边((x,y))，有(d_x+1ge d_y)，即(sum_{i=y}^{x-1}q_ile 1)
那么如果有一条长度为(-1)的边((x,y))，有(d_x-1ge d_y)，即(sum_{i=x}^{y-1}q_ige 1)
那么我们就可以根据这个性质搞一个DP，令(f_{i,j})表示考虑完了前(i)个(q)，满足(q_i=1)，且上一个为(1)的是(j)。我们考虑枚举下一个为(1)的位置(k)
考虑哪些边要被删掉，首先是长度为(1)的边，且满足(r>k,i<l<j)的((r,l))
其次是长度为(-1)的边，且满足(j<l<rle k)的((l,r))
然后发现这两个限制的代价和都可以前缀和预处理出来，因此复杂度就是(O(n^3))
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=505;
const long long INF=1e18;
int n,a[N][N]; long long s1[N][N],s2[N][N],f[N][N],ans=INF;
int main()
{
RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i)
for (j=1;j<=n;++j) if (i!=j) scanf("%d",&a[i][j]);
for (i=1;i<=n;++i) for (j=i+1;j<=n+1;++j)
for (s1[i][j]=s1[i][j-1],k=i;k<j;++k) s1[i][j]+=a[k][j];
for (i=1;i<=n;++i) for (j=n;j>i;--j)
for (s2[i][j]=s2[i][j+1],k=1;k<=i;++k) s2[i][j]+=a[j][k];
for (i=0;i<=n+1;++i) for (j=i;j<=n+1;++j) f[i][j]=INF;
for (f[0][0]=i=0;i<=n;++i) for (j=i;j<=n;++j) if (f[i][j]!=INF)
for (k=j+1;k<=n+1;++k) f[j][k]=min(f[j][k],f[i][j]+s1[j+1][k]+s2[j][k+1]-s2[i][k+1]);
for (i=0;i<=n;++i) ans=min(ans,f[i][n+1]); return printf("%lld",ans),0;
}
E - ABC String
太仙了不会做QAQ
F - Square Constraints
完全就是抄曲明姐姐的，题解可以去她博客看
贴一下基本一样的代码
#include<cstdio>
#include<utility>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=1005;
int n,mod,f[N],c[N],cnt,ans; pi t[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline int Mod(int x)
{
while (x>=mod) x-=mod; while (x<0) x+=mod; return x;
}
inline int F(CI x)
{
int y=0; while (y<(n<<1)&&x*x+y*y<n*n) ++y; return y;
}
inline int G(CI x)
{
int y=0; while (y<(n<<1)&&x*x+y*y<=(n<<1)*(n<<1)) ++y; return y;
}
int main()
{
RI i,j,k; scanf("%d%d",&n,&mod);
for (i=0;i<n;++i) t[++cnt]=mp(F(i),-i);
for (i=n;i<(n<<1);++i) t[++cnt]=mp(G(i),1);
for (i=0;i<n;++i) c[i]=G(i); sort(t+1,t+cnt+1);
//for (i=1;i<=cnt;++i) printf("%d%c",t[i],"
"[i==cnt]);
for (k=0;k<=n;++k)
{
memset(f,0,(k+1)<<2); f[0]=1; int s1=0,s2=0;
for (i=1;i<=cnt;++i) if (t[i].se==1)
{
for (j=0;j<=s2;++j) f[j]=1LL*f[j]*Mod(t[i].fi-s1-j)%mod; ++s1;
} else
{
for (j=s2;~j;--j) inc(f[j+1],1LL*f[j]*Mod(t[i].fi-s1-j)%mod),
f[j]=1LL*f[j]*Mod(c[-t[i].se]-(n+k+s2-j))%mod; ++s2;
}
//printf("%d %d
",k,f[k]);
if (k&1) inc(ans,Mod(-f[k])); else inc(ans,f[k]);
}
return printf("%d",ans),0;
}
Postscript
完了我发现我现在什么都不会了