心得简记 – G@rage

【数论】一道神奇的数论题

随意写下两个正整数 $2 < x, y < 99$
A知道其乘积，B知道其和。

A：我不知道这两个数，但我确定B也不知道
B：我也不知道这两个数，但我确定A也不知道
A：我知道了
B：我知道了
问：这两个数是多少

先假设 $s=x+y,t=xy$

A第一句话首先表明了t肯定有大于一种合法的分解方法。
A的第二句话说“B不知道”，说明了 $s \in [7,195]$ ，因为如果s=5则只能为2+3，其他数同理。
B的第一句话证明了A第二句话的是正确的。
B的第二句话确定“A不知道”，说明 $s=x+y$ 无论写成什么形式， $t=xy$ 都不可能只有一种分解方法，也就是说 $s$ 肯定不是两个质数的和。

到此位置可以得到一些数，这些数可能是s

11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 … Read the rest

【二分-贪心】问题集合

二分这类问题通常需要猜结论乱搞，解决此类问题的方法，就是见多识广

Q1

题意是说一个船会随风飘动，风的方向有周期。船每天也可以选择往一个方向自由航行，效果和风叠加，类似矢量。问最少多少天能到目的地。

做法是二分天数。天数定了，船如果不动，终点就是定了的。再此基础上船还可以走天数这么多步。如果和目的地的距离小于这个步数就缩减天数。

单调性：对于mid天，如果能达到，那么大于mid天也肯定能达到，因为多出的天数船可以想办法每天抵消风的影响呆在原地。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
int n, dirx[maxn], diry[maxn], desx, desy,inix,iniy;
string s;
int main()
{
    cin >> inix >> iniy >> desx >> desy;
    if(inix == desx && iniy == desy)
    {cout<<0;return 0;}
    cin >> n >> s;
    for(int i = 1; i <= n; i++ )
    {
        if(s[i - 1] == 'U') diry[i] = 1;
        if(s[i - 1] == 'D')

… Read the rest

【欧拉函数||容斥】gcd之和

Description
给出一个数列，求数列中任意一对数的最大公因数之和。
最大公因数的定义可以查看 baike.baidu.com/item/最大公因数 

Input
 多组数据。
输入的第一行包括一个整数表示数据组数T(1< =T<=10)。
每组数据的第一行包括一个整数表示数列的长度N(1<=N<=10000)。
第二行包括N个整数，第i个整数表示数列的第i个数ai(1<=ai<=10000)。

Output
每组数据在单独的一行中输出数列中任意一对数的最大公因数之和。 

Sample Input
3
3
2 1 3
4
4 3 9 6
7
7 7 7 7 7 7 7
Sample Output
3
13
147
HINT
 对于第一组数据:


gcd(2,1)+gcd(2,3)+gcd(1,3)=1+1+1=3

对于第二组数据:

gcd(4,3)+gcd(4,9)+gcd(4,6)+gcd(3,9)+gcd(3,6)+gcd(9,6)=1+1+2+3+3+3=13

对于第三组数据:

gcd(7,7)*(6+5+4+3+2+1)=7*21=147

关于这题有很多种解法。

1.容斥

假设d为N公因数，那么公因数之和就是所有的d乘上 $C$ $2 \choose num(d)$ ，其中num(d)指的是d出现的次数。因为任意两个数才有公约数，从有d这个公因数的所有数中选择两个即可。

然而这下算出来的是所有公因数的和，我们需要的是最大公因数的和。所以要除重，可以利用容斥原理。d算出的答案减去d的倍数算出的答案即为最大公约数之和。例如最大公因数为2的，就可以算出公因数为2的，再减去公因数和为4，8，16...的。倒过来容斥就可以了。

代码见题解 F

2.欧拉函数

首先欧拉函数有个性质： $n = \sum\limits_{d|n}φ(d)$ 也就是说n的所有因数的欧拉函数之和等于n本身。

假设 $gcd(x,y)=n$ ，则x,y小于n的公约数一定是相同的。可以得到：任意两数的gcd等于他们的公因数的欧拉函数值之和。则同样有某个gcd的和为

$n*C$ $2 \choose num(n)$

其中 $2 \choose num(n$ 可以看作是0..num(n)-1的等差求和公式： $0+1+2+..+num(n)-1$ 。n则可以写为 $\sum\limits_{d|n}φ(d)$

$(0+1+2+..+num(n)-1) * \sum\limits_{d|n}φ(d)$

可以看出每个公因数的Φ值乘上自己出现的次数都会对gcd的和做出一定贡献。而且因为每个d都有对应的gcd，所以不存在重复的情况。

那每加入一个数x。可以把答案加上 $num(k) * \sum\limits_{k|x}φ(k)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+233;
ll phi[maxn+23]={0};
ll a[maxn+23];
vector<ll> d[maxn+23];
void phi_t()
{
    for(ll i=2;i<=maxn;i++) phi[i]=0;
    phi[1]=1;
    for(ll i=2;i<=maxn;i++) 
        if(!phi[i])
        {
            for(ll j=i;j<=maxn;j+=i)
            {
                if(!phi[j])

… Read the rest

【离线并查集】问题集合

有 N 个数，初始均为 0。有 Q 个操作，第 i 个操作会把第 Li 到第 Ri 个数改为 Ci。问，所有操作结束后，每个数的值

并查集维护每个点右边最近的未修改的点，把操作全部读入以后倒序处理，因为是倒着处理所以每个点只能被修改一次，直接用数组记录就可以了。初始f[i]=i;当l..r合并以后区间内每个f[i]=i+1;查询函数加上路径压缩，当遇见一个被改变过的点可以立刻跳过后面所有被改变了的点

#include<iostream>
#include<stdio.h>
using namespace std;
int f[1001]={0};
int qm[1001][3]={0};
int a[1001]={0};
int n=0,q=0;
int ff(int x)
{
	if(f[x]==x) return x;
	else return f[x]=ff(f[x]);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n+2;i++) f[i]=i;
	for(int i=q;i>0;i--)
	{
		scanf("%d%d%d",&qm[i][1],&qm[i][2],&qm[i][0]);
	}
	for(int i=1;i<=q;i++)
	{
		int l=qm[i][1],r=qm[i][2],v=qm[i][0];
		while(l<=r)
		{			
			l=ff(l);
			if(l<=r)
			{
				a[l]=v;
				f[l]=l+1;
				l+=1;
			}
			else
			{
				break;
			}
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

… Read the rest

【数学-贪心-末状态已知】问题集合

蓝书 P4 分金币

https://vjudge.net/problem/UVA-11300

关于本题的“想一想为什么”：因为非齐次方程组的系数行列式为0，所以方程的解不唯一，所以最后一个方程没有贡献。

末态相同的题目，可以往方程组方向去想。最后可以往坐标的距离方面去靠。

蓝书 P7 雕塑

本题第一个设想“有一个雕塑不会动”的证明：

设开始每个墓碑相差A，移动后每个墓碑相差M，M可以不相同，因为有加进来的雕塑。设Xi为向下一个雕塑移动的距离。则有

[latex][/latex] $A-X_1+X_2=M =X_2=X_1-(A-M)$

$A-X_2+X_3=M =X_3=X_1-2(A-M)$

$\dots$

$A-X_n+X_1=M =X_n=X_1-n(A-M)$

同样可以变成X1到各个数字的距离最小的问题，即可知道X1在中位数的时候此时的距离为0。所以必然有一个雕塑它移动的距离为0。但不可用此方法求解答案，因为M仅仅是假设存在一个M使其满足末态，由于加入的雕塑不知道位置所以M无法确定。应采用贪心的方法求解… Read the rest

sort自定义comp不影响速度的写法

inline bool comp(const int &a,const int &b)
{
    return a>b;
}

… Read the rest

【优先队列-贪心】问题集合

中间商优化

http://codeforces.com/problemset/problem/867/E

一个长度为N的序列，代表每天股票的价格，每天只能执行买/卖/无动作三种操作。问如何才能赚得最多。

维护一个优先队列，队首存当前最小的价格，见到比最小的价格高的就先卖掉，并且把低价股票的价格变成当前价格，更低的就进队。如果以后遇到更高的可以和交易过的股票交易，也可以和没交易过的股票交易，它们赚的钱是一样的。。经过xyjj的指点知道了这类题的做法叫中间商优化，先找到更高的卖了提升价格，以后可以继续交易。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector> 
#include<utility>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > b;

ll n,t;
ll ans=0;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t);
		b.push(t);
		if(b.top()<t)
		{
			ans+=t-b.top();
			b.pop();
			b.push(t);
		}
	}
	printf("%lld",ans);
}

… Read the rest

2017寒假培训简记

… Read the rest

二分这类问题 通常需要猜结论乱搞，解决此类问题的方法，就是见多识广

二分这类问题通常需要猜结论乱搞，解决此类问题的方法，就是见多识广