打表¶
为什么把打表放在算法呢？因为很多情况下，我们也许很难找到规律。我们会去思考怎么样拼凑出答案，这是正向的。但是很多时候正向思考是很难的，所以我们就需要打表找规律。
结论题¶
为什么结论题板块会出现在打表里呢？因为有一些结论题其实就是打表找规律题目！！特别是看起来很复杂的结论题，一定要先打表找规律！！
例题 #1 LJJ 的石子¶
题目描述
LJJ 喜欢收集各种石子。经过 17 年的努力，如今他积攒了 n 个石子。
石子太多是一件麻烦的事情，为了方便管理，LJJ 希望把这 n 颗石子分成尽量少的堆， 使得每一堆的个数都形如 3n2−3n+1(n≥1)。LJJ 不会算，于是希望你来帮他算。
输入格式
第一行一个正整数 T(T≤1000)，为数据组数。
接下来 T 行，第 T 行一个整数 ni(ni≤1011)。
输出格式
T 行，每行一个整数表示答案。
样例输入 1
5
1
6
7
19
27
样例输出 1
1
6
1
1
3
数据范围
对于 100% 的测试点，\(n≤10^{11}\)。
我们发现可以选的数字都是\(6\times (i+1)\times i\div 2+i\)，所以我们猜测答案和\(n\bmod 6\)有关。一次我们打表后发现，如果余数是0,3,4,5，那么答案就是余数。否则：
-
余数是1，答案为1或者7
-
余数是2，答案为2或者8
那么什么时候会多出一个6呢？
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 1e5 + 5;
const int INF = 1e18;
const int M = 1e3;
const int MOD = 1e9 + 7;
inline bool check(int n){
n=(n-1)/3;;
int sq=sqrt(n);
return sq*(sq+1)==n;
}
//差是6的倍数
int f[N];
void solve(){
int n=rd;
int n6=(n-1)%6+1;
if(n6==1){
if(check(n))cout<<1<<endl;
else cout<<7<<endl;
}else if(n6==2){
int f=0;
for(int i=1;3*i*i-3*i+1<=n;i++){
if(check(n-3*i*i+3*i-1)){
f=1;
break;
}
}
if(f)cout<<2<<endl;
else cout<<8<<endl;
}else cout<<n6<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=rd;
// for(int i=1;i<20;i++)cdbg(a[i]);
while(T--){
solve();
}
return 0;
}
// 1 3 6 10 ...
例题 #2 [JSOI2015] 子集选取¶
题目描述
给定 \(n\) 个元素的集合 \(S= \left\{1,2,\cdots,n \right\}\) 和整数 $ k\(，现在要从 \(S\) 中选出若干子集 \(A_{i,j}\ (A \subseteq S\)，\)1 \le j \le i \le k)$ 排成下面所示边长为 \(k\) 的三角形（因此总共选出了 \(\frac{1}{2} k(k+1)\) 个子集）。
\(\begin{matrix} A_{1,1}\\ A_{2,1}&A_{2,2}\\ A_{3,1}&A_{3,2}&A_{3,3}\\ \vdots&\vdots&\vdots&\ddots\\ A_{k,1}&A_{k,2}&A_{k,3}&\cdots&A_{k,k} \end{matrix}\)
此外，JYY 对选出的子集之间还有额外的要求：选出的这些子集必须满足 \(A_{i,j} \subseteq A_{i,j-1}\) 且 \(A_{i,j} \subseteq A_{i-1,j}\)。 JYY 想知道，求有多少种不同的选取这些子集的方法。因为答案很大，JYY 只关心输出答案模 \(1{,}000{,}000{,}007\) 的值。
对于两种选取方案 \(A = \left\{ A_{1,1} , A_{2,1} ,\cdots, A_{k,k} \right\}\) 和 \(B = \left\{ B_{1,1} , B_{2,1} ,\cdots, B_{k,k} \right\}\) 只要存在 \(i,j\) 满足 \(A_{i,j} \neq B_{i,j}\)，我们就认为 \(A\) 和 \(B\) 是不同的方案。
对于 \(100\%\) 的数据，\(1 \le n\)，\(k \le 10^9\)。对 \(10^9+7\) 取模。
二话不说先打表，发现答案好像就是\(2^{kn}\)。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/v pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 3e5 + 5;
const int INF = 1e18;
const int MOD = 1e9 + 7;
itn ans=0;
int p[22][22];
int n,K;
void dfs(int x,int y){
if(y>x)x++,y=1;
if(x>K){
ans++;
return ;
}
for(int i=0;i<(1<<n);i++){
if(p[x-1][y]&&(i&p[x-1][y])!=p[x-1][y])continue;
if(p[x][y-1]&&(i&p[x][y-1])!=p[x][y-1])continue;
p[x][y]=i;
// dfs(x+1,y);
dfs(x,y+1);
}
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
b>>=1;
a=a*a%MOD;
}
return res;
}
void solve(){
n=rd,K=rd;
ans=0;
// 选择i是上面和左边的子集
// dfs(1,1);
// 这种题目必须**首先**打表找规律好吧
ans=ksm(2,n*K);
cout<<ans<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
例题 #3 数码¶
定义 S(n,k) 表示正整数 n 在 k 进制下的数码和，比如 S(13,3)=3,S(114514,1919810)=114514.
给定 n,K,x，你需要求出有多少个整数 k 满足 k∈[2,K],S(n,k)≤x。
输入格式
第一行一个数 T,表示数据组数
每一行三个正整数 n,K,x 描述一组数据
输出格式
对于每组数据输出一行一个数表示满足条件的数对数量。
对于所有的测试点 T=10，\(1≤n≤10^{12},1≤x,K≤10^{18}\)。
打表后发现S序列是由多个下降序列组成的。进一步发现k作为两个下降序列的分界当且仅当n/k和n/(k+1)的整数部分相差1.
于是我们根号分治，\(\sqrt n\)前的暴力，后面的求出序列的l,r然后二分。
注意K<n时在暴力时不可超过K（100→85pts）
/* Erica N */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int
#define rd read()
int read(){
int xx = 0, ff = 1;char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
const int N = 3e6 + 5;
const int INF = 1e18;
const int M = 1e6;
const int MOD = 1e9 + 7;
/*
S序列由多个递减序列组成。
分界线为l，x/l,x/(l+1)的个位恰好不同
*/
int cal(int x,int k){
int res=0;
while(x){
res+=x%k;
x/=k;
}
return res;
}
int check(int l,int r,int n,int x){
int tr=r;
int res=l-1;
while(l<=r){
int mid=l+r>>1;
if(cal(n,mid)>x)res=mid,l=mid+1;
else r=mid-1;
}
if(res<tr&&cal(n,res+1)>x)res++;
return tr-res;
}
void solve(){
int n=rd,K=rd,x=rd;
int B=sqrt(n);
int ans=0;
for(int i=2;i<=min(K,B+1);i++){
if(cal(n,i)<=x){
ans++;
}
}
int prer=0;
for(int i=B;i>1;i--){
int l=max(prer+1,max(B+2,n/i+1));
int r=min(n/(i-1),K);
if(l>K)break;
if(r<l)continue;
ans+=check(l,r,n,x);
prer=r;
}
if(K>n){
if(n<=x)ans+=K-n;
}
cout<<ans<<endl;
}
signed main() {
// freopen("digit.in","r",stdin);
// freopen("digit.out","w",stdout);
int T=rd;
while(T--){
solve();
}
return 0;
}