solve 6/11
补题：
Code:zz
Thinking:zz kk
把每个节点的深度都处理出来，同一深度的点的冲突度为 （x-1）,x为同层次点数减一。
然后冲突度不断下传（冲突度为3，则最多下传3层）
最后答案就是最后一层的深度加上冲突度。
#include<bits/stdc++.h>
#define CLR(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=;
int n,m;
int a[maxn];
bool vis[maxn];
ll ans[maxn],No[maxn];
struct egde{
int to,Next;
}e[maxn<<];
struct node{
int u;
ll time;
};
int head[maxn],tot;
void init(){
CLR(head,-),tot=;
CLR(vis,);
CLR(ans,);
CLR(No,);
}
void addv(int u,int v){
e[++tot].to=v;
e[tot].Next=head[u];
head[u]=tot;
}
void bfs(){
queue<node >q;
q.push({,});
vis[] = true;
ans[] = ;
if(a[])
{
No[]++;
}
while(!q.empty())
{
node s=q.front();
q.pop();
int u=s.u;
ll time=s.time;
for(int i=head[u];i!=-;i=e[i].Next)
{
int v=e[i].to;
if(!vis[v])
{
vis[v] = true;
q.push({v,time + });
ans[v] = time + + ;
if(a[v])
{
No[time + + ]++;
}
}
}
}
}
int main(){
while(cin>>n)
{
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
init();
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
addv(u,v),addv(v,u);
}
bfs();
ll aans = ,mm = ;
for(int i = ;i <= n;i++)
{
if(a[i])
{
mm = max(mm,ans[i]);
}
}
for(int i = ;i <= n;i++)
{
if(mm == i)
{
break;
}
No[i + ] += max((ll),No[i] - );
}
printf("%lld\n",No[mm] - + mm - );
}
}
Code:pai爷 zz kk
Thinking：pai爷 zz kk
根据式子观察得，这个式子就是斐波那契数列丢掉自己二进制的低位1的前缀和，也就是 fib n - lowbit（fib n），所以暴力打表把减掉的这部分打出来，找规律，然后矩阵快速幂求斐波那契数列前n项和，减一减。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
const int p=;
const int mod = ;
ll f[],sum[],r;
int t;
void mul(ll f[], ll a[][])
{
ll c[];
memset(c, , sizeof(c));
for (int j = ; j < ; j++)
for (int k = ; k < ; k++)
c[j] = (c[j] + (long long)f[k] * a[k][j]%mod) % mod;
memcpy(f, c, sizeof(c));
}
void mulself(ll a[][])
{
ll c[][];
memset(c, , sizeof(c));
for (int i = ; i < ; i++)
for (int j = ; j < ; j++)
for (int k = ; k < ; k++)
c[i][j] = (c[i][j] + (long long)a[i][k] * a[k][j]%mod) % mod;
memcpy(a, c, sizeof(c));
}
ll quickm(ll n){//求第n项和
ll f[] = { ,, };
ll tep=n-;
ll a[][] = { {,,},{,,},{,,} };
for (; tep; tep >>= )
{
if (tep & ) mul(f, a);
mulself(a);
}
return f[];
} ll solve(ll x,int w)
{
if(x==) return ;
if(x==) return ;
if(x==) return ;
if(x==) return ;
if(x==) return ;
if(x==) return ;
if(x==) return ;
for(int i=w;i>=;i--)
if(x>=1ll**f[i])
{
return (sum[i]+solve(x-*f[i],i-))%p;
}
}
int main()
{
f[]=;sum[]=;
for(int i=;i<=;i++)
{
f[i]=f[i-]*;
sum[i]=(sum[i-]*%p+f[i]*%p)%p;
}
scanf("%d",&t);
while(t--)
{
scanf("%lld",&r);
ll ans=solve(r,);
//printf("%lld\n",ans);
printf("%lld\n",(quickm(r)-ans+p)%p);
}
}
待补题 初中数学
Code:kk
Thinking:kk
先把每个b[ i ]的余数求出来，余数等于i的说明没有冲突，不等于i的，假设偏移量为px，说明他的前px项都在他前面，所以就得到拓扑序，由于要字典序最小，所以用优先队列求拓扑序列。
div2暴力建边即可，div1要线段树优化建边？待学习。
#include<bits/stdc++.h>
#include<unordered_map>
#define CLR(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=;
int n;
ll a[maxn],b[maxn],m[maxn];
int dg[maxn]; struct egde{
int to,Next;
}e[maxn*maxn];
int head[maxn],tot;
void init(){
CLR(head,-),tot=;
}
void addv(int u,int v){
e[++tot].to=v;
e[tot].Next=head[u];
head[u]=tot;
}
struct node{
int pos;
ll val;
friend bool operator <(const node &a,const node &b){
return a.val>b.val;
}
};
priority_queue<node >q;
void Top(){
int top=;
while(!q.empty()){
node s=q.top();
q.pop();
a[++top]=s.val;
for(int i=head[s.pos];i!=-;i=e[i].Next)
{
int pos=e[i].to;
dg[pos]--;
if(dg[pos]==)
{
q.push({pos,b[pos]});
}
}
}
}
int main(){
while(cin>>n)
{
init();
for(int i=;i<n;i++)
{
scanf("%lld",&b[i]);
m[i]=b[i]%n;
}
for(int i=;i<n;i++)
{
if(m[i]==i)
{
q.push({i,b[i]});
}else{
int px=(i-m[i]+n)%n;
while(px>)
{
addv((i-px+n)%n,i);
dg[i]++;
px--;
}
}
}
Top();
for(int i=;i<=n;i++)
{
printf("%lld%c",a[i],(i<n)?' ':'\n');
}
}
}
Code：pai爷
Thinking：pai爷
0(n*n)枚举每个数对有贡献的答案为不相同的最高位。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int p=;
int n,m,x,f[][];
int sum,ans=,chu,yu,a,b;
int main()
{
// freopen("1.txt","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&x);
int l=;
while(x>)
{
f[i][++l]=x%;
x/=;
}
f[i][]=l;
}
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
int k;
for(k=max(f[j][],f[i][]);k>=;k--)
if(f[i][k]!=f[j][k]) break; chu=m/(<<(k-));yu=m%(<<(k-));
a=(chu-chu/)*(<<(k-))-;b=chu/*(<<(k-)); sum=yu+;
//printf("chu=%d yu=%d a=%d b=%d sum=%d k=%d\n",chu,yu,a,b,sum,k);
if(chu%==) a+=sum,b=m-a;
else b+=sum,a=m-b;
if(f[i][k]==) ans=(ans+b)%p;
else ans=(ans+a)%p;
ans=(ans+p)%p;
//printf("%d\n",ans);
}
printf("%d\n",ans);
}
Code：zz
Thinking：zz
暴力枚举每个人是机器人的情况，再dfs查找出所有的机器人，选取机器人最少的情况。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<cmath>
#include<time.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<stack>
#include<bitset>
#include<unordered_map>
const int maxn = 0x3f3f3f3f;
const double EI = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354594571382178525166427;
const double PI = 3.141592653589793238462643383279;
using namespace std;
struct s
{
int k;
int c[];
}z[];
vector<int>ve[];
int vis[];
unordered_map<int,int>mp[];
inline void dfs(int pos)
{
int si,i;
si = ve[pos].size();
for(i = ;i < si;i++)
{
if(!vis[ve[pos][i]])
{
vis[ve[pos][i]] = ;
dfs(ve[pos][i]);
}
}
}
int main(void)
{
//ios::sync_with_stdio(false);
int n,m,i,j,ans,mi,l;
while(~scanf("%d %d",&n,&m))
{
for(i = ;i <= n;i++)
{
ve[i].clear();
mp[i].clear();
}
for(i = ;i < m;i++)
{
scanf("%d",&z[i].k);
for(j = ;j < z[i].k;j++)
{
scanf("%d",&z[i].c[j]);
}
}
for(i = ;i < m;i++)
{
for(j = z[i].k - ;j >= ;j--)
{
for(l = j - ;l >= ;l--)
{
if(!mp[z[i].c[j]][z[i].c[l]])
{
mp[z[i].c[j]][z[i].c[l]] = ;
ve[z[i].c[j]].push_back(z[i].c[l]);
}
}
}
}
ans = ;
for(i = ;i <= n;i++)
{
memset(vis,,sizeof(vis));
vis[i] = ;
dfs(i);
mi = ;
for(j = ;j <= n;j++)
{
if(vis[j])
{
mi++;
}
}
ans = min(ans,mi);
}
printf("%d\n",ans);
}
return ;
}
求补图，然后dp？待补
Code：pai爷
Thinking：pai爷
暴力打表？待补
赛后总结
kk：今天是演员的一天，演队友演自己，开局A题就想错了思路，然后一直想错，两小时才把A题这水题做了，然后E题基本读完题意，稍微写写就得到正解了，结果建边数组少开了，re一发，给队友写个矩阵快速幂的板子，没注意数据范围，long long写成了int，tle一发。影帝影帝，以后演技要好一些，要注意细节。
pai爷：模数复制粘贴错误找了一个小时的bug而且还wa了三发。找规律速度不够快。
zz：这场比赛演技越来越好了，水题想了好多假算法，而且wa以后才发现。找规律的题贡献了一个表。