Cover in Water
题目大意：我们有一排房间，一些房间是空的，一些房间是阻塞的，现在需要将所有的空房间都填满水，我们能做的只有两个操作：1.往一个空房间内放入水；2.将一个房间中的水取出放入另一个房间。另外当一个房间的左右两个房间都有水的时候，这个房间会自己产生水，我们需要尽可能地减少操作1的执行次数，问最少需要多少次操作1.
思路：由于左右两个房间有水，中间那个房间会自然产生水，所以可以发现如果有3个连在一起的房间，那么我们只需要放入两份水，中间空一个空房间，那么这个空房间产生水，我们把它移到别的空房间，那么它又会产生新的水，即只要有大于等于三个房间连在一起，那么就可以无限产生水，否则就要一个一个房间放入。那么我们需要统计的只有两个值，一个是空房间的总数，一个是是否有大于等于3个的空房间连在一起。
#include<bits/stdc++.h>
using namespace std;
char s[200];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d%s",&n,s);
char c=s[0];
int cnt,sum;
int mx=0;
if(c=='#') cnt=sum=0;
else cnt=sum=1;
for(int i=1;i<n;i++)
{
if(s[i]=='.')
{
sum++;
if(s[i]==c) cnt++,mx=max(cnt,mx);
else cnt=1,mx=max(cnt,mx);
}
else cnt=0;
c=s[i];
}
if(mx>=3) printf("2\n");
else printf("%d\n",sum);
}
}Laura and Operations
题目大意：黑板上有若干个数，只有1，2，3三种，我们每次可以选择两个不同的数并擦除，然后添加一个不同于两者的数，问最后能否使黑板上所有的数都相同，如果有可能，那么会是哪些数。输入给出三个数各自的数量，输出只用输出0，1（0表示这个数最终不可能出现，1表示这个数最终有可能出现）
思路：首先，如果有两个数的个数相等，那么第三个数一定可以得到，否则，我们来仔细考虑一下，不管怎么样就算两个不相等，也要想办法使它们相等，该怎么使它们相等呢，一个方法是用目标数字和多的那个来生成少的那个，最后使两者相等，多的减少的和少的增加的是一样多的，那么就证明它们的差值是偶数；另外如果目标的数量太少没办法使两者相等怎么办，我们可以先将两个都减少，用来生成目标，然后再用目标和多的去生成少的，使多的和少的数目相等，那么条件也是它们的差值是偶数。至此问题解决，核心就是要另外两个相等，或者能变成相等的。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b==c||(b+c)%2==0) printf("1 ");
else printf("0 ");
if(a==c||(a+c)%2==0) printf("1 ");
else printf("0 ");
if(b==a||(b+a)%2==0) printf("1 ");
else printf("0 ");
printf("\n");
}
}Anji's Binary Tree
题目大意：有一颗n节点的二叉树，1是根节点，我们对于每个节点输出它的左子节点和右子节点（0表示该节点为空），同时每个节点有一个字母，U表示返回父节点，R表示移动到右子节点，L表示移动到左子节点，如果该操作不合法则停止不动。我们想到任意一个叶子节点（没有子节点的点）去，可以修改任意一个节点处的操作，问最少修改多少次可以保证我们最终可以到达叶子节点。
思路：本来想的是记录所有的叶子节点，以及每个点的父节点的下标及到这个子节点需要进行的操作，我们遍历所有的叶子节点，并往回找知道访问到1，当父节点处的实际操作和到叶子节点的操作不同时，操作数自增，对于每个叶子节点求出需要的操作数，从中取最小值，理论上每个样例的时间复杂度是nlogn，不应该超时，但是很不幸，还是超时了。而且没办法优化，所以只能换思路。我们刚刚的思路是从后往前找，既然不成立，那么只能考虑遍历二叉树，用动态规划的思想来更新到每个节点的操作数，最后从所有叶子节点的操作数中找出最小值。实际上我感觉相比前一种方法，我们还多遍历了一些点，因为前一种方法不在路径上的点不会被遍历到，这种方法所有的点都会被遍历（这里分析有问题，前面的点会被反复访问），但是很奇怪，这个方法确实没有超时，并且AC了。不对，时间复杂度不能这么分析。
我重新分析了下，过程如下：
for(int i=0;i<e.size();i++) { int x=e[i]; int op=0; while(x!=1) { if(s[v[x].first]!=v[x].second) op++; x=v[x].first; } mi=min(mi,op); if(!mi) break; }这个是第一种方法的查找部分，我们假设一下一共有m层，每层都是满的，即n=2^m-1，那么就有2^(m-1)个叶子节点，每个叶子节点需要执行m次while(),那么时间复杂度就是m*2^(m-1),log(n+1)*(n+1)/2,即相当于nlogn,但是对于第二种方法，dfs只会把所有节点遍历一遍，时间复杂度是n,所以实际上还是快一点，所以应该是这个logn被卡了。
#include<bits/stdc++.h>
using namespace std;
char s[300010];
int l[300010],r[300010];
int dp[300010];
void dfs(int x)
{
if((!l[x]&&!r[x])||!x) return;
dp[l[x]]=dp[r[x]]=dp[x];
if(s[x]=='L') dp[r[x]]++;
else if(s[x]=='R') dp[l[x]]++;
else dp[l[x]]++,dp[r[x]]++;
dfs(l[x]);
dfs(r[x]);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
scanf("%s",s+1);
vector<pair<int,char>>v(n+10);
vector<int>e;
for(int i=1;i<=n;i++) l[i]=r[i]=dp[i]=0;
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
l[i]=a,r[i]=b;
if(!a&&!b) e.push_back(i);
}
dfs(1);
int mi=n+10;
for(int i=0;i<e.size();i++)
{
int x=e[i];
mi = min(mi,dp[x]);
}
printf("%d\n",mi);
}
}ps:对于二叉树，遍历比访问路径的效率更高，修改可以用dp来累计和转移。
Small GCD
题目大意：有一个数组a[],我们定义运算f(x,y,z):将x,y,z排序使x<=y<=z,f(x,,y,z)=gcd(x,y),求
思路：我们可以发现一些数比如最小的两个，在它们同时与其他数组合的时候，f()的值始终是它们俩的最大公因数，所以我们想到排序，将循环从三维降成二维，那么总的时间复杂度就是t*n*n，看上去能卡着过去，但实际上gcd的时间复杂度也要考虑，gcd(x,y)的时间复杂度即O(log(min(x,y))),所以我们即使优化了，还是照样超时（如果n的范围是<=3e3就可以实现）。所以，我们就要想新的方法来优化。
这题需要用到数论里的欧拉反演。本题欧拉反演部分的证明
核心的转化如下：
我感觉代码更直观，我就将链接中的公式推演全部转化成代码了，就从上一个思路的末尾开始讨论详细转化如下：
for(int j=1;j<=n;j++)
{
for(int i=1;j<=j-1;j++)
{
ans += gcd(a[i],a[j])*(n-j);
}
}
//欧拉公式
int sum=0;
for(int i=1;i<=n;i++)
{
if(n%d==0) sum += phi(d);
}
=>sum==n;
|
V
for(int j=1;j<=n;j++)
{
for(int i=1;j<=j-1;j++)
{
for(int d=1;d<=m;d++)
if(gcd(a[i],a[j])%d==0) ans += phi(d)*(n-j);
}
}
for(int j=1;j<=n;j++)
{
for(int d=1;d<=m;d++)
{
for(int i=1;j<=j-1;j++)
{
if(gcd(a[i],a[j])%d==0) ans += phi(d)*(n-j);
}
}
}
for(int j=1;j<=n;j++)
{
for(int d=1;d<=m;d++)
{
for(int i=1;j<=j-1;j++)
//if(gcd(a[i],a[j])%d==0)这个条件成立的话，phi(d)*(n-j)会被加入ans一次，[]这个有0和1两种值，刚好用来替换if
{
ans += [d|gcd(a[i],a[j])]*phi(d)*(n-j);
}
}
}
for(int j=1;j<=n;j++)
{
for(int d=1;d<=m;d++)
{
for(int i=1;j<=j-1;j++)
{
//d可以被两者的最大公因数整除，自然也可以被两者分别整除
ans += [d|a[i]]*[d|a[j]]*phi(d)*(n-j);
}
}
}
for(int j=1;j<=n;j++)
{
for(int d=1;d<=m;d++)
{
if(a[j]%d==0)//将[d|a[j]]替换成if判断
{
for(int i=1;j<=j-1;j++)
{
ans += [d|a[i]]*phi(d)*(n-j);
}
}
}
}
//令sum([d|ai])(1<=i<=j-1)=g(d)
for(int j=1;j<=n;j++)
{
for(int d=1;d<=m;d++)
{
if(a[j]%d==0)
ans += g(d)*phi(d)*(n-j); //g(d)相当于1-(j-1)中d的倍数的个数
}
}
//d是a[j]的因数，我们可以先将它预处理出来，得到v[a[j]]数组，那么就不用循环所有的数，只用循环v[a[i]]数组即可
for(int j=1;j<=n;j++)
{
for(auto d:v[a[j]])
{
ans += g(d)*phi(d)*(n-j);
}
}
//另外由于g(d)表示的是数组中的数在1~(j-1)范围内d的倍数的个数，那么我们直接在从小到大遍历的过程中统计一下即可
for(int j=1;j<=n;j++)
{
for(auto d:v[a[j]])
{
ans += g(d)*phi(d)*(n-j);
//a[j]是d的倍数，那么g[d]++；
g[d]++;
}
}现在需要计算phi(d),计算参考了线性筛计算欧拉函数，核心代码如下：
phi[1]=1;
for(int i=2;i<=N;i++)
{
if(!st[i]) phi[i]=i-1,prime.push_back(i);
for(auto j:prime)
{
if(i*j>N) break;
st[i*j]=1;
if(i%j)
{
phi[i*j]=phi[i]*(j-1);
}
else
{
phi[i*j]=phi[i]*j;
break;
}
}
}另外g(d)的计算也涉及到一些技巧，g(d)的含义是a[1]-a[j-1]之间d的倍数有多少个，挨个统计太麻烦，我们前面已经预处理了每个a[i]的因子，那么我们访问一个a[i]的时候，它所有因子的倍数多出现了一个，那么我们就将它所有因子d的g[d]++，那么g[d]同样能表示d的倍数的出现次数。至此所有细节都讨论清楚了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int phi[N+10],g[N+10],a[N+10];
vector<int>prime,v[N+10];
int st[N+10];
int main()
{
phi[1]=1;
for(int i=2;i<=N;i++)
{
if(!st[i]) phi[i]=i-1,prime.push_back(i);
for(auto j:prime)
{
if(i*j>N) break;
st[i*j]=1;
if(i%j)
{
phi[i*j]=phi[i]*(j-1);
}
else
{
phi[i*j]=phi[i]*j;
break;
}
}
}
for(int i=1;i<=N;i++)
{
for(int j=i;j<=N;j+=i)
{
v[j].push_back(i);
}
}
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
memset(g,0,sizeof g);
long long ans=0;
for(int j=1;j<=n;j++)
{
for(auto d:v[a[j]])
ans += 1ll*g[d]*phi[d]*(n-j),g[d]++;;
}
printf("%lld\n",ans);
}
}
