「DROI」Round 2
期望得分
T1 : \(100\)pts , T2 : \(30\)pts , T3:\(10\)pts , T4:\(0\)pts
实际得分
因为是 IOI 赛制，提交了就能看到分数，所以也是这个分数
用时情况
T1 : \(20\)min , T2:\(2.5\)h , T3:\(40\)min , T4:\(0\)min
T1
这个题比较好想，对于成立的 \(x\) ，设 \(x = qy + k(0\leq k < y)\)，这样满足 \(x \ \text{mod} \ y = k\)的条件，然后 \((q+1)y + k = n\)。
\[(q+1)y = n-k \]\[y = \frac{n-k}{q+1} \]所以当 \(q=0\) 时，\(y\) 最大，最大为 \(n-k\)，所以如果 \(n-k\leq k\)，\(y\leq k\)，这是不符合定义的，无解。
否则可以构造 \(x=k,y=n-k\) 这一组数据。
100pts
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
int T,n,k,p,t;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il void Main()
{
n = read() , k = read();
if(n-k > k)
cout << k << " " << n-k << "\n";
else puts("-1");
return ;
}
signed main()
{
T = read();
while(T--) Main();
return 0;
}
T2
题目意思给的十分不清晰，导致手摸样例手摸不出来，最后只能打 \(n\leq 5\) 的暴力。
理解题意后考场上想的是计算深度不超过 \(2\) 的森林。但其实再抽象一下就是一个图里面每个点，要么出度为 \(0\)，要么入度为 \(0\) 的图的个数。
但其实这样忽略了一种情况：二元环，所以单独讨论。最后合并起来。
设 \(f(x)\) 表示答案，\(t(2x)\) 表示从 \(2x\) 个点中构成 \(n\) 个二元环的方案数，\(g(x)\) 表示 \(n\) 个点不考虑二元环的单图数，则答案为
\[f(n) = \sum_{2i\leq n}C_n^{2i}\cdot t(2i) \cdot g(t-2i) \]接下来考虑怎么求 \(t(2x)\)，高中的均等随机分配问题，先前没涉猎过，所以推的时候比较困难。答案就是从 \(2x\) 中选 \(2\) 个，再从剩下的 \(2x-2\) 个中选 \(2\) 个，以此类推。不过这样是有顺序的，最后要除以 \(x!\)。答案就是
\[t(2x) = \frac{C_{2x}^2C_{2x-2}^2\dots C_2^2}{x!} \]然后这个式子其实就是
\[\prod_{2i < 2x}(2i+1) \]这一步不是很理解，得再问一问。
然后考虑如何求 \(g(x)\) ，首先 \(x\) 个点可以分为有入度和没入度的两类，设有入度的有 \(y\) 个，那么没有入度的就有 \(x-y\) 个点，每个没入度的都可以向每个有入度的连一条边，但最后每个有入度的点不能没有连接它的，所以每个有入度的点的方案数就是 \(2^{x-y}-1\) ，一共 \(y\) 个点，乘法原理，一共有 \((2^{x-y}-1)^y\) 种情况。那么
\[g(x) = \sum_{i=0}^xC_n^i\cdot (2^{x-i}-1)^i \]\(T\) 组数据,\(T,n\leq 1000\)。就可以先 \(O(n^2)\) 预处理出组合数，再 \(O(n)\) 预处理出 \(t\) 数组，\(O(n^2\log n)\) 处理出 \(g\) 数组，这样查询的时候就是 \(O(n)\) 的了，总复杂度就是 \(O(n^2\log n + Tn)\) ，可以通过。
30pts代码
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e3 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
int T,n,mod,G[N][N],p[N];
int cnt = 0;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il bool check()
{
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
G[i][j] = 0;
for(re int i=1;i<=n*n;i++)
{
if(p[i])
{
if(!(i%n)) G[i/n][n] = 1;
else G[i/n+1][i%n] = 1;
}
}
for(re int i=1;i<=n;i++)
for(re int j=1;j<=n;j++)
{
if(G[i][j])
{
for(re int k=1;k<=n;k++)
if(G[j][k]) return false;
}
}
return true;
}
il void dfs(int id)
{
if(id == n*n+1)
{
if(check()) cnt = (cnt+1) % mod;
return ;
}
p[id] = 1;
dfs(id+1);
p[id] = 0;
dfs(id+1);
}
il void Main()
{
n = read();
if(n == 2) cout << 4;
else cout << 108;
//dfs(1);
}
signed main()
{
T = read() , mod = read();
while(T--) Main();
return 0;
}
100pts代码
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e3 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
int t[N],g[N],C[N][N];
int T,mod,ans,d;
int n;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il int ksm(int a,int b)
{
int res = 1;
while(b)
{
if(b&1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res % mod;
}
il void init()
{
C[0][0] = 1;
for(re int i=1;i<=1000;i++)
{
C[i][0] = 1;
for(re int j=1;j<=i;j++) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}
t[0] = 1 , g[0] = 1;
for(re int i=2;i<=1000;i+=2) t[i] = t[i-2] * (i-1) % mod;
for(re int x=1;x<=1000;x++)
{
for(re int i=0;i<=x;i++)
{
d = ksm(2,x-i);
g[x] = (g[x]%mod + C[x][i] * ksm(d-1,i)) % mod;
}
}
}
il void Main()
{
n = read() , ans = 0;
for(re int i=0;i<=n;i+=2) ans = (ans + C[n][i]%mod*t[i]%mod*g[n-i]) % mod;
cout << ans << "\n";
}
signed main()
{
T = read() , mod = read();
init();
while(T--) Main();
return 0;
}
T3
晚上补题主要卡在 T2 这个计数上了，T3没咋看，粗略看了一下好像是个诈骗题。明天补一下。
10pts 爆搜code
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 155;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
int val[N][N],a[N],c[N],k;
int refer[N],id;
bool vis[10005];
int n,cnt,cntl,cntr,ans;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il void dfs(int len,int sum)
{
if(len == n)
{
ans = max(ans,sum);
return ;
}
for(re int i=refer[0];i!=0;i=refer[i])
{
if(c[i])
{
c[i]--;
dfs(len+i,sum+val[len+1][len+i]);
c[i]++;
}
}
}
signed main()
{
n = read();
for(re int i=1;i<=n;i++) a[i] = read();
for(re int i=1;i<=n;i++)
{
c[i] = read() , cnt += i*c[i] , k += c[i];
if(c[i] != 0) refer[id] = i , id = i;
}
refer[id] = 0;
if(cnt != n) { cout << -1; return 0; }
vis[0] = 1;
for(re int i=1;i<=100;i++) vis[i*i] = 1;
for(re int l=1;l<=n;l++)
for(re int r=l;r<=n;r++)
{
cntl = cntr = 0;
for(re int i=l;i<=r;i++) if(vis[abs(a[i]-a[l])]) cntl++;
for(re int i=l;i<=r;i++) if(vis[abs(a[r]-a[i])]) cntr++;
val[l][r] = cntl * cntr;
}
dfs(0,0);
cout << ans;
return 0;
}
T4
主席树的一个题，还没学到，磕 T2 太久了导致没看 T4，数据结构的暴力比较好拿，先补完 T3。
标签：ch,return,int,28,long,DROI,2023.5,getchar,define From： https://www.cnblogs.com/bloodstalk/p/17439093.html