1. noip模拟试题(三)-初音未来
可以发现n范围较小,m范围较大,复杂度应与m无关。
考虑n^2算法,由于要进行区间排序所以想到冒泡。
冒泡排序是交换相邻逆序对,而逆序对最多n^2个,每交换一对,可能会减少一个然后增加两个相邻逆序对,但在全局一定是减少的。因此最多进行n^2次交换,复杂度n^2
使用set维护每个(i,i+1)逆序对的i的位置,每次区间排序在指定区间中找到所有逆序对,新产生的也要交换。
2. noip模拟试题(一)-乘
发现q不超过1e7,故直接将b数组暴力求解。
之后如果暴力计算,需要 1e7*log(1e12) 的复杂度,看似能过实则爆炸。
之后考虑优化,求 $a^b$ 的时候,b由于对l取模,故不超过 1e12。
进行数论分块,求出 $a^1 ~ a^{1e6}$ (p1数组) 以及 $a^{2 * 1e6} ~ a^{1e6 * 1e6}$ (p2数组)
之后求 $a^b$ 用两个求出来的进行拼接即可。ll tmp=(p1[b%M]*p2[b/M])%p;
3. noip模拟试题(二)-树
这个与luogu上题目 上帝造题的七分钟 / 花神游历各国 是类似的思路,暴力modify
数据结构,发现用懒标记根本无法转化 1 信息。考虑暴力修改,若一个区间所有数或和再或k等于k,这个区间就无修改必要。
我不知道这样为什么不会超时,问问同学
之后3解出期望式子与区间和 和 区间每个数的平方的和有关。
注意操作2没让取模巨坑。
4. noip模拟试题(三)-信标
怎么解释捏
玄学树形dp,理解了就容易了,放个代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
int n,g[N],d[N];
int h[N],e[N],ne[N],idx,f[N];//邻接表双倍数组
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
d[a]++;d[b]++;
}
void dfs(int x,int last){
int cnt=0,t=0;
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(j==last) continue;
dfs(j,x);cnt++;
g[x]+=g[j];
f[x]+=f[j];
t+=(g[j]==1);
}
f[x]+=max(t-1,0);
if(!cnt) g[x]=1;
}
int main(){
memset(h,-1,sizeof(h));
scanf("%d",&n);
if(n==1){
printf("0");
return 0;
}
for(int i=1;i<n;i++){
int a,b;scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
int cnt2=0,cnt4=0;
for(int i=1;i<=n;i++){
if(d[i]==2) cnt2++;
else if(d[i]==4) cnt4++;
}
if(cnt2==2&&cnt4==n-2){
printf("1");
return 0;
}
dfs(1,-1);
printf("%d",f[1]);
return 0;
}
特判链的情况。