A. 三元
这东西虽然过了，但是感觉它好鬼畜啊，既没有用到三进制数，也没有把所有串的单个位拿出来讨论，我的dfs只是为了生成全排列……就这玩意还写了177行……
什么鬼？
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 3;
int n, L, cnt[17][4], b[17], tot, id[4];;
bool flag;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int qpow(int a, int b)
{
int ans = 1;
while(b)
{
if(b & 1) ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}
void pt()
{
for(int i=1; i<=L; i++)
{
printf("%d", b[i]);
}
printf("\n");
tot++;
if(tot == n) flag = 1;
}
void dfs2(int a)
{
if(a > L)
{
pt(); return;
}
for(int i=0; i<=2; i++)
{
b[a] = i;
dfs2(a+1);
if(flag) return;
}
}
void qqq()
{
for(int i=1; i<=L; i++)
{
cnt[i][b[i]]--;
printf("%d", b[i]);
}
printf("\n");
tot++;
if(tot == n) flag = 1;
}
void dfs4(int a)
{
if(a > L)
{
qqq(); return;
}
for(int i=1; i<=3; i++)
{
b[a] = id[i];
dfs4(a+1);
if(flag) return;
}
}
void ppp()
{
for(int i=1; i<=L; i++)
{
if(!cnt[i][b[i]]) return;
}
for(int i=1; i<=L; i++)
{
cnt[i][b[i]]--;
printf("%d", b[i]);
}
printf("\n");
tot++;
if(tot == n) flag = 1;
}
void dfs5(int a)
{
if(a > L)
{
ppp(); return;
}
for(int i=1; i<=3; i++)
{
if(!cnt[a][id[i]]) continue;
b[a] = id[i];
dfs5(a+1);
if(flag) return;
}
}
int main()
{
freopen("three.in", "r", stdin);
freopen("three.out", "w", stdout);
n = read(); L = read();
cnt[1][0] = cnt[1][1] = n;
for(int i=2; i<=L; i++)
{
int c0 = qpow(3, L-i);
if(c0 >= n)
{
cnt[i][1] = cnt[i][2] = n;
}
else if(c0 + c0 >= n)
{
cnt[i][0] = n - c0;
cnt[i][1] = c0;
cnt[i][2] = n;
}
else if(c0 + c0 + c0 >= n)
{
cnt[i][0] = cnt[i][1] = n - c0;
cnt[i][2] = c0 + c0;
}
else
{
int w = c0+c0+c0, t = n / w;
cnt[i][0] = cnt[i][1] = cnt[i][2] = n - t * c0;
t = n % w;
if(c0 >= t)
{
cnt[i][0] -= t;
}
else if(c0 + c0 >= t)
{
cnt[i][0] -= c0; cnt[i][1] = cnt[i][1] - t + c0;
}
else
{
cnt[i][0] -= c0; cnt[i][1] -= c0;
cnt[i][2] = cnt[i][2] - t + c0 + c0;
}
}
}
id[1] = 1; id[2] = 2; id[3] = 0;
b[1] = 0; dfs4(2);
id[1] = 2; id[2] = 0; id[3] = 1;
b[1] = 1; tot = 0; flag = 0; dfs5(2);
flag = 0; tot = 0; b[1] = 2; dfs2(2);
return 0;
}
D. 矩形
第二个鬼畜是h=1的特判，由于翻转过分复杂导致Cat赛时锅了，把L，R和二分的结果和填进去的数字都换成了相反的？前缀和和组合数之类的没有想到……
什么鬼？
inline ll get_end(ll col) {return col*(col+1)/2;}
inline bool checkL(ll mid) {return get_end(mid) < L;}
inline bool checkR(ll mid) {return get_end(mid) < R;}
int k[N], m;
void solve()
{
L = read(), R = read();
ll sum = 1ll * n * (n+1) / 2;//等号后面不开ll，会挂！！
L = sum - L + 1, R = sum - R + 1;
ll l1 = R, r1 = L;
int l = 0, r = n;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(checkL(mid)) l = mid;
else r = mid - 1;
}
int st = l + 1;
l = 0, r = n;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(checkR(mid)) l = mid;
else r = mid - 1;
}
int ed = l + 1, ss = ed;
ll pos = l1;
st = n - st + 1; ed = n - ed + 1;
for(int col=ed; col>=st && pos<=r1; )
{
k[++m] = col;
if(pos == get_end(ss)) col--, ss++;
pos++;
}
reverse(k+1, k+1+m);
for(int i=1; i<=m; i++) printf("%d ", k[i]);
exit(0);
}标签：cnt,return,NOIP,--,鬼畜,mid,int,c0,ll From： https://www.cnblogs.com/Catherine2006/p/16892912.html