【题解】牛客CSP-S提高组赛前集训营4

日常T1被降智.jpg

日常t1过大样例爆零（你们的大样例都是假的 ***）

求出题人加强数据卡掉我第二题 的代码，让我有动力去补正解，谢谢。https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41606129

哪里可以下数据吗，本地自造数据和大样例过了结果爆零233

T2我的做法是 n 遍dfs，求出所有距离为 p,q 的点对，然后丢进两个set里去重，最后枚举set，用LCA判断是否交叉，这样 n^4 log n 居然水了50分...

看不太透啊

请问出题人提供std吗😳

难受的就是想出来的都是正解，但是因为时间不够打不完而爆零，在考场上会正解没打出来和不会没有区别

我T1还写***树我怕不是憨憨

T2不是上一次说的换根DP吗，为啥要用lca？

看不太透啊

T2大样例是错的为啥不早说，我到考试结束都不知道T2大样例是错的，害的我调试T2心态炸了，大样例死活过不去！！！

#include<cmath> #include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<cstring> #include<map> #include<queue> #include<set> #include<vector> #include<bitset> #define int __int128 #define ll __int128 using namespace std; const int maxn=300005; const long long mod=1e9+7; int n; ll k,sum,a[maxn],shika[maxn],f1,f2,f3,erci,yici,changshu; map<ll,ll>pre; inline ll read() {     ll x=0,f=1;     char ch=getchar();     while(ch<'0'||ch>'9')     {         if(ch=='-')             f=-1;         ch=getchar();     }     while(ch>='0'&&ch<='9')     {         x=(x<<1)+(x<<3)+(ch^48);         ch=getchar();     }     return x*f; } inline void write(ll a) {     if(a<0)     {         char a='-',b='1';         putchar(a);         putchar(b);     }     else     {         if(a>=10)             write(a/10);         putchar(a%10+'0');     } } void jiefangcheng(int f1,int f2,int f3) {     erci=(f3+f1-2*f2)/2;     erci%=mod;     yici=f2-f1-3*erci;     yici%=mod;     changshu=f1-erci-yici;     changshu%=mod; } signed main() {     n=read(),k=read();     for(int i=1;i<=n;++i)         a[i]=a[i+n]=a[i+2*n]=read();     for(int i=1;i<=3*n;++i)     {         if(pre.find(a[i])==pre.end())             pre[a[i]]=0;         shika[i]=(shika[i-1]+pre[a[i]])%mod; //      cout<<shika[i]<<' ';         sum=(sum+i*(i+1)/2-shika[i])%mod;         if(i==n)             f1=sum;         if(i==2*n)             f2=sum;         if(i==3*n)             f3=sum;         pre[a[i]]=i;     }     jiefangcheng(f1,f2,f3); //  cout<<f1<<' '<<f2<<' '<<f3<<endl; //  cout<<erci<<' '<<yici<<' '<<changshu<<endl;     write(((erci*k%mod*k%mod+yici*k%mod+changshu)%mod+mod)%mod);     return 0; } 90分求助

T1没开long long变成30分了我自闭了

什么时候牛客可以提供赛后的数据下载。。。。。

@nqiiii 大佬可以解释下T2第一种情况的是怎么做的吗？我们枚举a,b就已经是了，然后还需要枚举lca(a,b)子树内的每个点就是O（n3）了 是我哪里还没理解吗？或者给个STD也可以

有没有t2写的这样的树dp啊  dp[i][j][[0/1][0/1]表示以i为根的子树中，包括根在内有j个点连成一条链可以往父节点继续连，子树内其他部分是否已经选了长度为p的链和长度为q的链的方案树 求个ac代码。。。过了大样例然而60

jxcakak

T3不是可以先预处理出所有im， 1in 这样就不需要用组合数了

T2大样例问了楼主，满怀期望的等了5分钟，等来了个no response→_→（手调大样例令人快乐