$题目大意$

${求}\sum_{i=1}^{n}\sum _{j=1}^{m}{lcm(i,j)} {且} 1\le n,m\le 1e7$

${正解:}$

${有}{lcm(i,j)=\frac{i\cdot j}{\gcd(i,j)}}$

${所以原式为:}$

$ans(n,m)=\sum_{i=1}^{n}\sum _{j=1}^{m}{\frac{i\cdot j}{\gcd(i,j)}}$

$~\qquad\qquad =\sum_{i=1}^{n}\sum _{j=1}^{m}{ \sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})}{}{\frac{i\cdot j}{d}}}$

${现在需要将d给提出来,默认}{n\le m,}{我们设}i=i'\cdot d,j=j'\cdot d,{则}i'=\frac{i}{d},j'=\frac{j}{d},将i,j替换进上式得:$

$ans(n,m)=\sum_{d=1}^{\min(n,m)}{\sum_{i'=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j'=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i',j')=1]\cdot d\cdot i'\cdot j'}}}$

$~\qquad\qquad=\sum_{d=1}^{n}{d\cdot\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i,j)=1]\cdot i\cdot j}}}$

${接着将d后面的部分再提出来考虑,化简枚举约数,运用莫比乌斯反演:} [\gcd(i,j)=1]=\sum_{d\mid gcd}{\mu{(d)}}:$

${设} \ {g(n,m)}=\sum_{i=1}^{n}{\sum_{j=1}^{m}{[\gcd(i,j)=1]\cdot i\cdot j}}$

$~\qquad\qquad=\sum_{d=1}^{n}{\sum_{d\mid i}^{n}{\sum_{d\mid j}^{m}{\mu(d)\cdot i\cdot j}}}$

${再设}\ i=i' \cdot d,j=j' \cdot d \ {带入,将}\mu{提出来}$

${即}\ g(n,m)=\sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}\cdot{\sum_{i=1}^{\left\lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{i\cdot j}}}}$

$~\qquad\qquad = \sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}}\cdot\frac{{\left \lfloor \frac{n}{d} \right \rfloor}\cdot ({\left \lfloor \frac{n}{d} \right \rfloor}+1)\cdot {\left \lfloor \frac{m}{d} \right \rfloor}\cdot({\left \lfloor \frac{m}{d} \right \rfloor}+1)}{4}$

${最后将g(n,m)带入ans(n,m)中得:}$

$ans(n,m)=\sum_{d=1}^{n}{d}\cdot{g(\left\lfloor \frac{n}{d}\right\rfloor,\left\lfloor \frac{m}{d}\right\rfloor)}$

${用数论分块求出来}~{g(n,m)}~{再用数论分块求出来}~{ans(n,m),}~{就在{\Theta(n+m)内}}{得到答案了}~{(∠・ω< )⌒★}$

通信线路 题解

题目描述

见 通信线路

整体思路

只是一个最小生成树的模板题，数据量也没有很大

第一种方法：kruskal算法

两种实现：边集数组：时间复杂度$O(M log M + M(N + M))$；饼查集 并查集：时间复杂度$O(M log M + kM)$。

第二种方法：Prim算法

时间复杂度：$O(N^2)$（heap优化$O(M long M)$）

读者可以自行实现

代码实现

最小生成树的两个主要算法都可以在讲义中找到，点击这个

本题解采用并查集 + kruskal

好孩子不可以抄代码哦

#include <bits/stdc++.h> // 万能头
using namespace std;
int n; // n是城市数
const int N = 1510,M = 1e4 + 10; // N是最大城市数，M是最大边数
struct Edge // 将边的参数定义到结构体里
{
	int x,y,w; // x起点，y终点，w是权重
}e[M];
bool cmp(Edge &a,Edge &b) // 排序按照权重从小到大
{
	return a.w < b.w;
}
int f[N]; // 并查集数组
void init()
{ // 并查集初始化
	for(int i = 1; i <= N; ++i) f[i] = i;
}
int get(int x)
{ // 递归地查询x属于哪个集
	if(x == f[x]) return x;
	return f[x] = get(f[x]);
}
void merge(int x,int y)
{ // 将两个集合并
	int fx = get(x),fy = get(y);
	if(fx != fy) f[fy] = fx;
}
void kruskal()
{ // kruskal本体
	init(); // 初始化
	int ans = 0;
	for(int i = 1;i <= M;i++)
	{
		int x = e[i].x,y = e[i].y,w = e[i].w; // 每次从边集中取出一个权重较小的
		if(get(x) != get(y)) // 如果这条边的两个顶点不属于同一个集（就是不相连的意思）
		{
			merge(x,y); // 合并，即采用这条边
			ans += w; // 总和记得加哦O(∩_∩)O
		}
	}
	cout << ans << endl; // 输出就好乐，也可以返回ans在主函数里输出
}
int main()
{
	freopen("mcst.in","r",stdin); // 文件输入输出
	freopen("mcst.out","w",stdout);
	cin >> n; // 输入城市数
	int ind = 0;
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < n;j++)
		{
			int op; // 双重循环读入输入的矩阵（确信
			cin >> op; // 第i+1个顶点到第j+1顶点之间边的权重
			if(op != -1) e[ind].x = i + 1,e[ind].y = j + 1,e[ind].w = op,ind++;
			// 如果两个顶点可以有边相连，就放在边集数组
		}
	}
	sort(e,e+M,cmp); // 用cmp来排序
	kruskal(); // kruskal，启动！
	return 0; // 记得return是美德
}

有一说一，其实挺水

做一个以身高为关键字的单调栈储存每个奶牛的序号，再单独以一个数组存储身高，在弹出时处理它对答案的贡献，显然为当前序号到它的序号的差减一

最后注意一下数据大小开个longlong

#include<bits/stdc++.h>
using namespace std;

int n,a[110086],tmp,c[110086],num;

int main () {
    freopen("hair.in","w",stdin);
    freopen("hair.out","r",stdout);

    cin>>n;
    
    for(int i = 1; i<=n; i++){
        int y;
        cin>>y;
        
        while(y>=c[a[tmp-1]]&&tmp>0){
            num+=i-a[tmp-1]-1;
            tmp--;
        }
        c[i]=y;
        a[tmp++]=i;
    }
    while(tmp>0){
    if(a[tmp-1]!=n)num+=n-a[tmp-1];
    tmp--;
    }
    cout<<num;
    return 0;
}

考场一个小时切不出来T1于是暴力及时止损，看题解才想到的贪心，，

首先我们要知道，对任意数列进行有限次邻项交换后，必定能得到该数列的全排列。这样你就拿到了 $n\leq10$ 的20分。

如果你能想到在 $t_1$ 和 $t_2$ 中的由连续的1组成的连通块内，对应的 $s_1$ 与 $s_2$ 的部分可以任意排列，那你就拿到了 $t_1=t_2$ 的20分。

如果你能想到当 $s_1$ 全是0或1的时候不管 $s_2$ 如何排列答案都不会变，那你就拿到了性质A的20分。

（性质C太难了不讨论了）（）（）

暴力的60分该拿还是得拿的）

然后是正解

从前往后扫，如果这个位置 $s_1$ 和 $s_2$ 有一个不能能换，那就从对应连通块内挑一个数放上去配对就好了

如果都能换，同上，挑0挑1都一样

如果都不能换，直接算答案

感性地贪一下，如果这个位置不配对，那就是给后面的位置留了一个0或1，但这个数在后面至多也只有1的贡献，还不如拿到就马上配了（

换之前记得先看看这个块剩下的0和1数量还够不够

（其实用并查集维护会方便一点）

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof a)
#define rev(x) reverse(x.begin(),x.end())
using namespace std;
struct node{
	int n0,n1;
	node operator+(const node&q)const{return (node){n0+q.n0,n1+q.n1};}
}siz[100010][2];
int fa[100010][2];
inline int find(int x,int p){
	if(x==fa[x][p]) return x;
	return fa[x][p]=find(fa[x][p],p);
}
inline void merge(int x,int y,int p){
	x=find(x,p),y=find(y,p);
	if(x!=y) siz[y][p]=siz[y][p]+siz[x][p],fa[x][p]=y;
}
int main(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		string s1,s2,t1,t2;cin>>s1>>s2>>t1>>t2;
		for(int i=0;i<n;i++) fa[i][0]=fa[i][1]=i;
		for(int i=0;i<n;i++){
			siz[i][0].n0=s1[i]=='0';
			siz[i][0].n1=s1[i]=='1';
			siz[i][1].n0=s2[i]=='0';
			siz[i][1].n1=s2[i]=='1';
		}
		for(int i=1;i<n;i++){
			if(t1[i]=='1'&&t1[i-1]=='1') merge(i-1,i,0);
			if(t2[i]=='1'&&t2[i-1]=='1') merge(i-1,i,1);
		}
		

		int ans=0;
		for(int i=0;i<n;i++){
			int p1=find(i,0);
			int p2=find(i,1);
			if(siz[p1][0].n0>0&&siz[p2][1].n0>0) siz[p1][0].n0--,siz[p2][1].n0--,ans++;
			else if(siz[p1][0].n1>0&&siz[p2][1].n1>0) siz[p1][0].n1--,siz[p2][1].n1--,ans++;
		}
		cout<<ans<<endl;
	}
	
	
	return 0;
}

挺不错的题，原题是 CF 的某个题，但我找不到题号了，所以写个比较易懂的题解方便补，可能废话很多。

首先要有一点初步的观察，可以发现 $\max$ 的求解是很方便的，我们只需要找出所有 $k$ 的倍数，这样一定能让 $\gcd$ 尽可能为 $k$，并且使取的数的个数最多。

然后是最小值。这仍然需要一些观察和经验。我们想要每个取的数都不是 "无用" 的，也就是说，它必须能帮我们 "赶出去" 某些没有用的素因子。

下面是一些经验。假设一开始随便选了一个数 $x(k|x)$，再选一个数 $y(k|y)$，那么必然有 $\gcd(x, y)<x$，否则 $y$ 不如不选。那么有 $\frac{x}{\gcd(x, y)}\ge 2$，因为最小的素因子是 2。

于是我们知道，选数的最小个数其实是 $\mathcal O(\log \max(S_i))$ 级别的，在这道题里面也就 18 个左右。

面对最优化问题关于答案范围的极强约束，一般地，直接枚举答案，转化为 $\forall s\in [1, 18]$，对于 $1\sim n$ 的每个 $k$ 判断是否 "存在" 一种取出 $s$ 个数使得 $\gcd$ 为 $k$ 的方案。

然后是这道题非常巧妙的一个点，一般我们很少遇到判定比计数还困难的题目，这道题就是一个例子。

那怎么办？直接换成计数来做。意识到这一点需要有莫比乌斯反演的功底，这样才能在面对着一个和计数没有关系的题目时，通过诸如 $\gcd = k$ 这样的条件感受出做法。这也给我们启示，有时我们需要用这样的数学直观刺激直觉。

于是我们先枚举 $s$，计算 $F(k,s)$ 表示选 $s$ 个数使得 $\gcd$ 是 $k$ 的倍数，这是简单的，假设原序列有 $p$ 个数是 $k$ 的倍数，那么 $F(k,s)=\mathrm C_{p}^{s}$。$p$ 的计算可以使用狄利克雷后缀和解决，实质上就是高维前缀和的一种拓展。

接下来的操作很平凡，使用莫比乌斯反演，得 $G(k,s)$，即原本要求的方案数，为 $\sum\limits_{k|x}F(x,s)\times \mu(x/k)$。

时间复杂度 $\mathcal O(m\ln m\log m)$。题解好像写的有点魔怔，可能是文化课学多了导致思维也比较呆。

NOIp2017 时间复杂度 题解

分析

模拟，模拟，还是模拟。

给定了 $n$ 行 A++ 代码和一个小明算的时间复杂度，判断此复杂度是否正确（$Yes$ 和 $No$）。

若代码存在语法问题（$F$ 与 $E$ 未匹配或变量名重复定义），则输出 $ERR$。

思路

循环可以嵌套，也可以并列，考虑用栈来模拟每一组循环。

使用两个栈，一个使用结构体维护循环信息 $st$，一个维护当前的时间复杂度信息 $opts$。

为了方便，开始之前先将 $opts$ 内压入一个 0。

（本题解时间复杂度表示中，$w$ 表示复杂度为 $O(n^w)$。）

接下来是模拟流程。

维护一个整数数组 $u$，$u_c$ 表示字符 $c$ 在此时被使用的次数。

如果读取到 $F$：

- 将循环的参数 $i$、$x$ 和 $y$ 压入 $st$；为方便，将 $n$ 看做 101。

- 如果此前参数 $i$ 已经被使用，则将 $isERR$ 设为 1；

- 将 $u_i$ 的值增加 1；

- 将 0 压入 $opts$。

如果读取到 `E`：

- 若此时栈空，即没有循环需要退出，$isERR$ 设为1；

- 否则弹出当前 $st$ 顶的循环，使用 $opts$ 栈顶更新 $opts$ 次顶的时间复杂度。弹出栈顶。将 $u_i$ 的值减少 1。

当 $l$ 行代码运行完毕，若 $st$ 栈内仍有元素，则将 $isERR$ 设为 1。

最后，判定算得结果是否与小明的答案相同即可。

更新时间复杂度

本题解将着重讲解一下时间复杂度的更新。

对于一层循环 ${i,x,y}$，其复杂度与内部的所有嵌套的子循环有关，且为所有嵌套的子循环中时间复杂度的最大值，再加上该循环自身的复杂度。

首先，若此循环中 $x>y$，即无法进入，则此循环及往下的复杂度一定为 $O(1)$，表示为 0；

若 $y=101$ 且 $x\neq 101$，则此循环的复杂度为 $O(n)$，表示为 1。

特别地，$x$ 与 $y$ 都为 101 时，此循环的复杂度仍记为 $O(1)$。

CODE

#include<bits/stdc++.h>
#define ll long long
#define rev(x) reverse(x.begin(),x.end())
#define lb(x) (x&(-x))
using namespace std;
struct node{
    char varName;
    int from,to;
    node(){
        varName=' ';
        from=to=0;
    }
    bool ableToRun(){
        return from<=to;
    }
};
int varNameIsUsed[26];
stack<node> st;
stack<int> opts;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
//	freopen("2017complexity.in","r",stdin);
//	freopen("2017complexity.out","w",stdout);
	
	int t;cin>>t;
	while(t--){
	    while(!st.empty()) st.pop();
	    while(!opts.empty()) opts.pop();
	    opts.push(0);
	    memset(varNameIsUsed,0,sizeof varNameIsUsed);
	    bool isERR=false;
	    
	    int ls;cin>>ls;
	    string ops;cin>>ops;
	    
	    for(int lne=1;lne<=ls;lne++){
	        char p;cin>>p;
	        if(p=='F'){
	            node wp;
	            cin>>wp.varName;
	            string fm,tm;cin>>fm>>tm;
	            if(fm=="n") wp.from=101;
	            else{
	                int nw=0;
	                for(int i=0;i<fm.length();i++) nw=nw*10+fm[i]-'0';
	                wp.from=nw;
                }
	            if(tm=="n") wp.to=101;
                else{
	                int nw=0;
	                for(int i=0;i<tm.length();i++) nw=nw*10+tm[i]-'0';
	                wp.to=nw;
                }
                
                if(varNameIsUsed[wp.varName-'a']) isERR=true;
                varNameIsUsed[wp.varName-'a']++;
                
	            st.push(wp);
	            opts.push(0);
	            
            }else{
                if(!st.empty()){
                    node tp=st.top();
                    st.pop();
                    
                    varNameIsUsed[tp.varName-'a']--;
                    
                    int nwOpt=(opts.top()+(tp.to==101&&tp.from!=101?1:0))*tp.ableToRun();
                    opts.pop();
                    int kkk=opts.top();
                    opts.pop();
                    kkk=max(kkk,nwOpt);
                    opts.push(kkk);
                }else{
                    isERR=true;
                }
            }
        }
        if(!st.empty()) isERR=true;
        
        int opsINT=0;
        if(ops=="O(1)") opsINT=0;
        else{
            for(int i=4;i<ops.length()-1;i++) opsINT=opsINT*10+ops[i]-'0';
        }
        
        if(isERR) cout<<"ERR"<<endl;
        else if(opsINT==opts.top()) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        
        
    }
	
	return 0;
}