清北提高组精英班Day1
一、基础数论
1、快速幂
2、矩阵乘法
struct matrix
{
int c[n][n];
};
matrix operator * (matrix a, matrix b)
{
matrix c;
for (int i=0; i<n; ++i)
for (int j=0; j < n; ++j)
c.c[i][j] = 0;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
c.c[i][j] = (c.c[i][j]+ a.c[i][k] * b.c[k][j]) % mod;
return c;
}
matrix pow(matrix a, int times)
{
matrix tmp = I;
while (times)
{
if (times & 1) tmp = tmp * a;
a = a * a;
times >>= 1;
}
return tmp;
}例题：
3、欧几里得（gcd）
int gcd(int a, int b)
{
if (b == 0) return a;
return gcd(b, a % b);
}4、拓展欧几里得（exgcd）
//ax + by = gcd(a,b) = tmp
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1; y = 0;
return a;
}
int tmp = exgcd(b, a % b, y, x); // b*y + (a%b)*x = gcd(a,b)
y = y - a / b * x;
return tmp;
}
int main()
{
int x, y;
cout << exgcd(3, 5, x, y) << endl;
cout << x << " " << y << endl;
return 0;
}5、最小公约数（LCM）
6、线性筛素数
7、欧拉函数
8、线性欧拉筛素数
9、费马小定理和欧拉定理
10、逆元
11、求逆元
12、线性求逆元
13、组合数
二项式定理
同余
组合数取模：问题一
利用杨辉三角求解
组合数取模：问题二
组合数取模：问题三
组合数取模：问题四
Lucas定理
组合数取模：问题五
中国剩余定理
组合数取模：问题六
14、高斯消元
•利用加减消元法解方程
•直接贴代码
二、NOIP模拟
1、
旅行（travel）
【问题描述】
Hhf喜欢旅行，他有n个目的地（都在一条直道上）。他计划开始一段旅行，hhf想去参观n个目的地（都在一条直道上）。hhf在起点开始他的旅行。第i个目的地和起点的距离为ai千米（ai为非负整数）。不存在两个目的地和起点的距离相同。
从第i个目的地走到第j个目的地所走的路程为 |ai-aj|千米。我们把参观n个目的地的顺序称作一次“旅行”。hhf可以参观他想要参观的任意顺序，但是每个目的地有且只能被参观一次（参观顺序为n的排列）。
hhf把所有可能的“旅行”都写在一张纸上，并且记下每个“旅行”所要走的路程。他对所有“旅行”的路程之和的平均值感兴趣。但是他觉得计算太枯燥了，所以就向你寻求帮助。
【输入格式】
第一行一个正整数n。
第二行n个非负整数a1,a2,....,an（1≤ai≤10^7）。
【输出格式】
两个整数，答案用最简分数形式输出，第一个为分子，第二个为分母。
【输入样例】
3
23 5
【输出样例】
22 3
【样例提示】
样例有6种可能的旅行：
[2, 3, 5]: 该“旅行”的路程：|2 – 0| + |3 – 2| +|5 – 3| = 5;
[2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5| = 7;
[3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| = 7;
[3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| = 8;
[5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| = 9;
[5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| = 8.
答案为 1/6 * （5+7+7+8+9+8）=44/6=22/3
【数据范围】
30% n<=10
50% n<=1000
100% n<=100000
旅行：
考虑将这些路径拆成许多的两点间的路径，考虑两点间的路径对答案的贡献。
先考虑起点到Ai这种路径，这条路径确定之后，后面的路径方案就与这条路径无关，后面的方案数一共有 (n-1)!，由于它是单向边且不能改变位置，所以这种路径对路径和的贡献为(n-1)!*Ai。
现在考虑任意两点路径Ai，Aj，除了这两个点的其他的n-2个点方案总数为(n-2)!，而我们可以将这条路径插入在任意的一个位置，共有n-1个位置，故这条路径的方案总数为(n-2)!*(n-1)即(n-1)!，对路径和的贡献为(n-1)!*abs(Ai-Aj)。
所以路径和就转化为求(n-1)!*Σabs(Ai-Aj)(1<=i,j<=N,i≠j)+(n-1)!*ΣAi。
问题的关键就是求这Σabs(Ai-Aj)。
将所有的Ai排序后，实际上只要考虑从大的点往小的点走，最后路径和*2即可。
然后考虑如何计算：
假设a1 > a2> a3 > a4，
以Ai为结尾的Ai-Aj的和为Si，
那么：
S2 = a1 - a2
S3 = a1 - a3 + a2 - a3 = (a1 - a2 + a2 -a3) + a2 - a3 = S2 + 2 *（a2 - a3）
S4 = a1 - a4 + a2 - a4 + a3 - a4 = (a1 - a3+ a3 - a4) + (a2 - a3 + a3 - a4) + (a3 - a4)
= S3 + 3 * (a3 - a4)
于是发现Si其实是可以递推的。
答案中分子的(n-1)!与分母的n!相约后只剩一个n，求出c=gcd(ans,n)再分别除以c输出即可。
#define maxn 100001
#define ll long long
using namespace std;
ll a[maxn];
ll n,s,ss,t;
char m;
ll gcd(ll a,ll b)
{
if(b==0)
{
return a;
}
else
{
gcd(b,a%b);
}
}
void write(ll ans)
{
if(ans>=10)
write(ans/10);
m=ans%10+'0';
cout<<m;
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s+=a[i];
}
sort(a+1,a+n+1);
for(ll i=1;i<=n;i++)
{
ss+=a[i]*(i-1);
ss-=a[i]*(n-i);
}
s+=ss*2;
t=gcd(s,n);
write(s/t);
cout<<" ";
write(n/t);
return 0;
}2、
度假村(resort)
【问题描述】
小P喜欢在度假村度过自己的暑假。度假村的村民都非常迷信，所以村子里只有黑色和白色的房子。黑色房子里的村民迷信奇数，他们只有在以自己的房子为一个端点的道路总数是奇数的时候才会高兴。而白色房子里的村民正好相反，只有是偶数的时候才会高兴。
不过现在村子里还没有道路，这让黑房子里的村民非常不高兴。于是交通部长决定修路。他有一张表格记录着能够建起来的路的信息，并且这些路在表格上是以递减的建造花费排序的。小P只想着有人赶紧把路建好，而村委会只想着能让所有人都高高兴兴。也就是对每个黑房子，以它为一个端点的路的总数是奇数，而对每个白房子正好相反。
村委会自然是想少花点钱。不过他们对便宜的定义也是不一般的。假设有两个道路方案的集合U和V，并且令集合S为所有在U中而不在V中的道路或在V中而不在U中的道路构成的集合。如果S中最贵的道路属于V，那么就说方案U比方案V便宜。
现在需要你来帮助他们找到让所有村民都高兴的最便宜的方案。
【输入】
输入第一行包括两个整数n和m，代表村中的房子数和可以建的道路数。
接下来一行包括n个字符。如果第i个字符是'B'代表i号房子是黑色的，如果是'W'则是白色的。不会有其他字符出现。
然后m行每行两个数字xk,yk，代表x号和y号房子间可以建编号为k的道路。道路是以建造价格降序排列的。并且保证任意一对房子之间不会有多于一条道路。
【输出】
输出一行一个数列为满足条件的道路的编号。升序输出，相邻两个之间由一个空格隔开。如果没有解，输出一行一个0。
【输入样例】
33
BBW
12
23
1 3
【输出样例】
23
【数据范围】
对于30%的数据，满足n <=1000，m <=1000。
对于100%的数据，满足n <=100000, m <= 100000。
using namespace std;
const int maxn = 200005;
struct arr
{
int adj, data, next;
};
int flag, check[maxn], top, ans[maxn], a[maxn], n, m, f[maxn], b[maxn][2];
char ch[maxn];
arr g[maxn];
int getf(int t)
{
if (f[t] == t) return t;
return f[t] = getf(f[t]);
}
int dfs(int t)
{
int tmp = 0;
check[t] = 1;
for (int p=a[t]; p; p=g[p].next)
if (!check[g[p].adj])
{
int cnt = dfs(g[p].adj);
if ( cnt % 2 == 0 )
ans[g[p].data] = 0;
tmp = tmp + cnt;
}
if (ch[t-1] == 'B')
tmp++;
// cout << t << " " << tmp << endl;
return tmp;
}
int main()
{
freopen("resort.in", "r", stdin);
freopen("resort.out", "w", stdout);
flag = 1;
scanf("%d%d", &n, &m);
scanf("%s", ch);
for (int i=1; i<=m; ++i)
scanf("%d%d", &b[i][0], &b[i][1]);
for (int i=1; i<=n; ++i) f[i] = i;
for (int i=m; i>=1; --i)
{
int x = getf(b[i][0]);
int y = getf(b[i][1]);
if (x != y)
f[x] = y, ans[i] = 1;
}
// for (int i=1; i<=m; ++i)
// cout << ans[i] << " "; cout << endl;
for (int i=1; i<=m; ++i)
if (ans[i])
{
g[++top].adj = b[i][0]; g[top].next = a[b[i][1]]; g[top].data = i; a[b[i][1]] = top;
g[++top].adj = b[i][1]; g[top].next = a[b[i][0]]; g[top].data = i; a[b[i][0]] = top;
}
for (int i=1; i<=n; ++i)
if (!check[i])
if (dfs(i) % 2 == 1)
flag = 0;
// for (int i=1; i<=m; ++i)
// cout << ans[i] << " "; cout << endl;
if (!flag) cout << "0" << endl; else
{
for (int i=1; i<=m; ++i)
if (ans[i])
printf("%d ", i);
cout << endl;
}
return 0;
}
3、
停车场(park)
【问题描述】
在一个停车场中有一排车位，从左到右编号为 1 到 n，初始时全部是空的。有若干汽车，进出停车场共 m 次。对于每辆进入停车场的汽车，会选择与其它车距离最小值最大的一个车位，若有多个符合条件，选择最左边一个。给定车辆进出的序列，依次输出每辆车的车位编号。
【输入说明】
第一行，两个整数 n 和 m，表示停车场大小和操作数；
接下来 m 行，每行两个整数，F 和 x
F 是 1 表示编号为 x 的车进停车场；
F 是 2 表示编号为 x 的车出停车场；
保证操作合法，即：
出停车场的车一定目前仍在停车场里；
停车场内的车不会超过 n；
【输出说明】
对于所有操作 1，输出一个整数，表示该车车位的编号。
【样例输入】
7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8
【样例输出】
1
7
4
2
7
4
1
3
【数据范围】
对30%的数据 n<=1000 ，m<=1000
对60%的数据 n<=200000，m<=2000
对100%的数据n，m<=200000，车的编号小于等于 10^6
此题需使用线段树进行维护；
30分：
#define maxnnn 200001
#define maxnnnn 1000001
#define ll long long
using namespace std;
ll a[maxnnn];
int b[maxnnnn];
int n,m,f,tot,c;
ll x;
int main()
{
freopen("park.in","r",stdin);
freopen("park.out","w",stdout);
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
scanf("%d%lld",&f,&x);
a[1]=x;
b[x]=1;
cout<<1<<endl;
for(int i=2;i<=m;i++)
{
int maxn=-0x3f3f3f;
scanf("%d%lld",&f,&x);
if(f==1)
{
for(int j=1;j<=n;j++)
{
int minn=0x3f3f3f;
if(a[j]==0)
{
for(int k=j-1;k>=1;k--)
{
if(a[k]!=0)
{
if(j-k<minn)
{
minn=j-k;
}
break;
}
}
for(int k=j+1;k<=n;k++)
{
if(a[k]!=0)
{
if(k-j<minn)
{
minn=k-j;
}
break;
}
}
if(minn>maxn)
{
c=j;
maxn=minn;
}
}
}
a[c]=x;
b[x]=c;
cout<<c<<endl;
}
else
{
a[b[x]]=0;
}
}
return 0;
}100分：
using namespace std;
const int MAXN=int(2e5)+10;
const int MAXB=int(1e6)+10;
int N,M,A,B,Np,Nlen,Nl,Nr,Mid;
int Len,Val[MAXN],Stl[MAXN],Str[MAXN],Pos[MAXN];
int Next[MAXN],Pre[MAXN],T[MAXB];
int Get() {
int Sign=0,Num=0;
char ch;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') break;
ch=='-'?Sign=1:Num=ch-48;
for (ch=getchar();ch>='0'&&ch<='9';ch=getchar()) Num=Num*10+ch-48;
return Sign==0?Num:-Num;
}
void Up(const int &x) {
int Now=x;
while (Now>1&&(Val[Now]>Val[Now>>1]||(Val[Now]==Val[Now>>1]&&Stl[Now]<Stl[Now>>1]))) {
swap(Val[Now],Val[Now>>1]);
swap(Stl[Now],Stl[Now>>1]);
swap(Str[Now],Str[Now>>1]);
Pos[Stl[Now]]=Now;
Pos[Stl[Now>>1]]=Now>>1;
Now=Now>>1;
}
return ;
}
void Down(const int &x) {
int Now=x,Son;
while ((Now<<1)<=Len) {
((Now<<1|1)>Len||Val[Now<<1]>Val[Now<<1|1]||(Val[Now<<1]==Val[Now<<1|1]&&Stl[Now<<1]<Stl[Now<<1|1]))
?Son=Now<<1:Son=Now<<1|1;
if (Val[Son]>Val[Now]||(Val[Son]==Val[Now]&&Stl[Son]<Stl[Now])) {
swap(Val[Son],Val[Now]);
swap(Stl[Son],Stl[Now]);
swap(Str[Son],Str[Now]);
Pos[Stl[Son]]=Son;
Pos[Stl[Now]]=Now;
Now=Son;
}
else break;
}
return ;
}
void Heap_Del(const int &x) {
int Dv=Val[x],Ds=Stl[x];
Val[x]=Val[Len];
Stl[x]=Stl[Len];
Str[x]=Str[Len];
--Len; Pos[Stl[x]]=x;
(Val[x]>Dv||(Val[x]==Dv&&Stl[x]<Ds))?Up(x):Down(x);
return ;
}
void Heap_Ins(const int &L,const int &R) {
++Len;
Stl[Len]=L; Str[Len]=R; Pos[L]=Len;
(L==1||R==N)?Val[Len]=R-L:Val[Len]=(R-L)>>1;
Up(Len);
return ;
}
void SetIO(string Name,const int &Opt) {
if (Opt==1) {
string in=Name+".in",out=Name+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
else {
fclose(stdin); fclose(stdout);
}
return ;
}
int main() {
SetIO("park",1);
N=Get(),M=Get();
Heap_Ins(1,N);
Next[1]=Pre[N]=N;
for (int i=1;i<=M;++i) {
A=Get(),B=Get();
if (A==1) {
Nl=Stl[1]; Nr=Str[1]; Heap_Del(1);
(Nl==1||Nr==N)?(Nl==1?Mid=1:Mid=N):Mid=(Nl+Nr)>>1;
T[B]=Mid; printf("%d\n",Mid);
if (Nl<Mid) Heap_Ins(Nl,Mid-1);
if (Mid<Nr) Heap_Ins(Mid+1,Nr);
Next[Nl]=Pre[Mid-1]=Mid-Nl;
Pre[Nr]=Next[Mid+1]=Nr-Mid;
Next[Mid]=Pre[Mid]=0;
}
else {
Np=T[B]; Nl=Np-Pre[Np-1]; Nr=Np+Next[Np+1];
if (Nl<Np) Heap_Del(Pos[Nl]);
if (Np<Nr) Heap_Del(Pos[Np+1]);
Heap_Ins(Nl,Nr);
Next[Nl]=Pre[Nr]=Nr-Nl+1;
}
}
SetIO("",2);
return 0;
}
上一篇： MySQL -Explain深度剖析及优化案例解析
下一篇： MySQL - 索引优化案例实操
推荐阅读