2022/7/31

707C - Pythagorean Triples

这玩意竟然是有公式的，竟然没推出来，，，

a为奇数时,b=（a²-1）/2,c=b+1，a为偶数是,b=a2/4-1 c=b+2.

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll a;
int main(){
    cin>>a;
    if(a<=2){
        printf("-1\n");return 0;
    }
    ll b,c;
    if(a&1){
        b=(a*a-1)/2;c=b+1;
    }
    else{
        b=a*a/4-1;c=b+2;
    }
    printf("%lld %lld\n",b,c);
    system("pause");
    return 0;
}

1307C - Cow and Message

算是前缀和类型的一道题吧，这次看了数据是不对的，以后会想不出反例来的，，，

其实要符合等差数列这个条件最好是两个字母的，其次再是一个字母，字母越多符合条件的数量就越少，所以要求两个字母的如果两个字母相同那就是C(n,2),如果两个字母不同那就要看一下顺序了，毕竟ab,ba不是同一个，可以设一个这样的数组vis[i][j]表示ij这个字符串出现的次数，因为两个数的数列都是等差数列所以直接统计次数就可以，之后用ans获取最大值就可以了

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
string s;
ll vis[30][30],cnt[30];
int main(){
    cin>>s;
    ll ans=0;
   for(int i=0;i<s.length();i++){
    cnt[s[i]-'a']++;
    for(int j=0;j<26;j++){
        vis[j][s[i]-'a']+=cnt[j];
    }
   }
   for(int i=0;i<26;i++) vis[i][i]=(cnt[i]-1)*cnt[i]/2LL,ans=max(ans,cnt[i]);
   for(int i=0;i<26;i++)
   for(int j=0;j<26;j++)
   ans=max(ans,vis[i][j]);
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

C - Zero Path dp

        如果n+m是偶数的话那么路径会有奇数步所以一定不对，设mx[i][j]为从1，1到i，j的路径中最大的为多少，mi[i][j]为最小的为多少，如果mi[n][m]<=0,mx[n][m]>=0，那么一定有解，这个也是可以证明的，大致的说一下就是你可以去修改路径上的一步让-1变为1或这相反，这代价会是-2，0，2中的一个，而mx和mi都是偶数，且0在[mi[n][m],mx[n][m]]中，所以总会有一条路径是可以的

C. Zero Path_跑路的菜的博客-CSDN博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll t,n,m,a[1005][1005],mx[1005][1005],mi[1005][1005];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) scanf("%lld",&a[i][j]),mx[i][j]=-1e18,mi[i][j]=1e18;
        mx[1][1]=mi[1][1]=a[1][1];
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(i>1) mx[i][j]=max(mx[i-1][j]+a[i][j],mx[i][j]),mi[i][j]=min(mi[i][j],mi[i-1][j]+a[i][j]);
            if(j>1) mx[i][j]=max(mx[i][j],mx[i][j-1]+a[i][j]),mi[i][j]=min(mi[i][j],mi[i][j-1]+a[i][j]);
        }
        if((n+m)%2==0) printf("NO\n");
        else{
            if(mi[n][m]<=0&&mx[n][m]>=0) printf("YES\n");
            else printf("NO\n");
        }
    }
    system("pause");
    return 0;
}

CF246E Blood Cousins Return - 启发式合并 

主要是如果统计不同的姓名，用一个map<pair<ll,string>,ll>来表示这个姓名在第几层是否出现过，然后就可以来计数了，因为删除计数的时候也得靠map来统计，所以map要多清空一次，也正因为这多的一次差点超时，，但要是关了同步流应该就没啥问题了

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll n,m,tot[200005],ans[100005];
ll son[100005],siz[100005],dep[100005],fson,f[100005];
ll head[200005],cnt;
string s[100005];
map<pair<ll,string>,ll>mp;
struct node{
    ll val,id;
};
vector<node>q[100005];
struct Edge{
    ll from,to,next;
}edge[200005];
void addedge(ll from, ll to){
    edge[++cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].next =head[from];
    head[from] = cnt;
}
void dfs1(ll u,ll fa){
    siz[u]=1;dep[u]=dep[fa]+1;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(siz[j]>siz[son[u]]) son[u]=j;
    }
}
void cal(ll u,ll fa,ll val){
    if(!mp[{dep[u],s[u]}]) tot[dep[u]]+=val,mp[{dep[u],s[u]}]=1;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=fa&&j!=fson) cal(j,u,val);
    }
}
void dfs2(ll u,ll fa,ll keep){
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=fa&&j!=son[u])  dfs2(j,u,0);
    }
    if(son[u]) dfs2(son[u],u,1),fson=son[u];
    cal(u,fa,1);
    fson=0;
    for(int i=0;i<q[u].size();i++) ans[q[u][i].id]=tot[dep[u]+q[u][i].val];
    if(!keep) mp.clear(),cal(u,fa,-1),mp.clear();
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        cin>>s[i]>>f[i];
        if(f[i]) addedge(i,f[i]),addedge(f[i],i);
    }
    for(int i=1;i<=n;i++) if(!f[i]) dfs1(i,0);
    scanf("%lld",&m);
    for(int i=1;i<=m;i++){
        ll v,k;
        scanf("%lld%lld",&v,&k);
        q[v].push_back(node{k,i});
    }
    for(int i=1;i<=n;i++) if(!f[i]) dfs2(i,0,0);
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    system("pause");
    return 0;
}

CF1009F Dominant Indices - 洛谷 | 启发式合并

大部分都是对的，但是在统计深度的时候出现了错误，不应该统计差，应该直接统计深度，然后最后输出的时候再做差，因为直接统计差的话程序就直接比较差的最小值了，这显然是不对的

题解 CF1009F 【Dominant Indices】 - EI psy congroo! - 洛谷博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll n,m,tot[MAX],ans[MAX];
ll son[MAX],siz[MAX],dep[MAX],fson;
ll head[MAX<<1],cnt;
struct node{
    ll val,id;
};
vector<node>q[MAX];
struct Edge{
    ll from,to,next;
}edge[MAX<<1];
void addedge(ll from, ll to){
    edge[++cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].next =head[from];
    head[from] = cnt;
}
void dfs1(ll u,ll fa){
    siz[u]=1;dep[u]=dep[fa]+1;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(siz[j]>siz[son[u]]) son[u]=j;
    }
}
ll maxx,dis;
void cal(ll u,ll fa,ll val,ll x){
    tot[dep[u]]+=val;
      
    if(tot[dep[u]]>maxx){
        maxx=tot[dep[u]],dis=dep[u];
        //if(x==1) cout<<tot[dep[u]]<<" "<<maxx<<endl;
    }
    else if(tot[dep[u]]==maxx) dis=min(dep[u],dis);
    //cout<<tot[dep[u]]<<" sss "<<u<<" "<<x<<" "<<maxx<<" "<<dis<<endl;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=fa&&j!=fson) cal(j,u,val,x);
    }
}
void dfs2(ll u,ll fa,ll keep){
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=fa&&j!=son[u])  dfs2(j,u,0);
    }
    if(son[u]) dfs2(son[u],u,1),fson=son[u];
    cal(u,fa,1,u);
    //cout<<ans[u]<<" "<<u<<endl;
    fson=0;
    ans[u]=dis;
    if(!keep) cal(u,fa,-1,u),maxx=0,dis=0;
}
int main(){ 
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v);addedge(v,u);
    }
    dfs1(1,0);
    dfs2(1,0,0);
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]-dep[i]);
    system("pause");
    return 0;
}

CF375D Tree and Queries - 洛谷 | 启发式合并

一发入魂，关键是要怎样处理大于等于k的颜色有多少种，可以发现每种颜色在计数时，每个颜色的每个数值只会出现一次，也就是说现在a颜色出现了5次，下一次再出现的话一定是又出现了一次变成了6次，那么我们就可以设一个这样的数组vis[i]，表示出现了大于等于i次的颜色有多少个，询问的时候就可以直接加上了，具体看代码吧

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll n,m,tot[MAX],ans[MAX],c[MAX];
ll son[MAX],siz[MAX],dep[MAX],fson;
ll head[MAX<<1],cnt;
struct node{
    ll val,id;
};
vector<node>q[MAX];
struct Edge{
    ll from,to,next;
}edge[MAX<<1];
void addedge(ll from, ll to){
    edge[++cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].next =head[from];
    head[from] = cnt;
}
void dfs1(ll u,ll fa){
    siz[u]=1;dep[u]=dep[fa]+1;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(siz[j]>siz[son[u]]) son[u]=j;
    }
}
ll vis[100005];
void cal(ll u,ll fa,ll val){
    ll x=tot[c[u]];
    tot[c[u]]+=val;
    if(val==-1) vis[x]+=val;
    else vis[tot[c[u]]]+=val;
    //if(tot[c[u]]==4) cout<<u<<" sss "<<val<<endl;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=fa&&j!=fson) cal(j,u,val);
    }
}
void dfs2(ll u,ll fa,ll keep){
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j!=fa&&j!=son[u])  dfs2(j,u,0);
    }
    if(son[u]) dfs2(son[u],u,1),fson=son[u];
    cal(u,fa,1);
    //cout<<ans[u]<<" "<<u<<endl;
    fson=0;
    //if(u==1)  for(int i=1;i<=10;i++) cout<<vis[i]<<" "<<i<<endl;
    for(int i=0;i<q[u].size();i++) ans[q[u][i].id]=vis[q[u][i].val];
    if(!keep) cal(u,fa,-1);
}
int main(){ 
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    for(int i=1;i<n;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v);addedge(v,u);
    }
    for(int i=1;i<=m;i++){
        ll u,k;
        scanf("%lld%lld",&u,&k);
        q[u].push_back(node{k,i});
    }
    dfs1(1,0);
    dfs2(1,0,0);
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    system("pause");
    return 0;
}