[ABC248F] Keep Connect - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:原题解abc 248 F 题解 - 洛谷专栏 (luogu.com.cn)
//int dp[2][9003][2]; 删除i条边,考虑第j条边--nope
Keep Connect
https://www.luogu.com.cn/problem/AT_abc248_f
不知道怎么定义dp数组,怎么转移? 感觉比较确定的就是有一维是删除i条边..数组的定义一定要完整,严谨..
看了洛谷的题解,还是懵..
https://www.luogu.com.cn/article/au39xwvu 洛谷题解
顶级..顶级..想不到第三维的这样定义..
主要是确定dp怎么定义.
感觉有点状压的意思.
int n,p;
int dp[3003][3003][2];定义! dp[i][j][0/1]为考虑前i列,删除j条边,前i列是否联通0/1,的方案数为dp[i][j][0/1]
void solve(){ G dp..cin>>n>>p;dp[1][0][1]=1,dp[1][1][0]=1; initfor(int i=1;i<=n-1;i++){for(int j=0;j<=n-1;j++){ j从0开始.前i列图已经连通(dp[i+1][j+2][0]+=dp[i][j][1]*2)%=p;(dp[i+1][j+1][1]+=dp[i][j][1]*3)%=p;(dp[i+1][j][1]+=dp[i][j][1])%=p;前i列图不连通(dp[i+1][j+1][0]+=dp[i][j][0])%=p;//(dp[i+1][j+1][1]+=dp[i][j][0]*2)%=p; 这样会使图断开，并且连不回去(dp[i+1][j][1]+=dp[i][j][0])%=p;}}for(int j=1;j<=n-1;j++) cout<<dp[n][j][1]<<" ";
}[ABC175D] Moving Piece - 洛谷
思路:因为n只有5000,并且每个点的入度出度最多为1，不是最多，是必然。 并且！！图上一定是有至少一个环的!! 那么可以o(n^2),枚举起点,找到所在环的大小及sum,然后枚举终点,记录答案. 枚举终点不是从全部枚举!而是从该点所在的环中的点枚举 枚举不是乱枚举。美妙的枚举。 还优化了score数组,vct直接存来到当前点的sum.
int n,k;
int to[5005];
int arr[5005];
[ABC175D] Moving Piece
https://www.luogu.com.cn/problem/AT_abc175_d
题解:因为n只有5000,并且每个点的入度出度最多为1，不是最多，是必然。 并且！！图上一定是有至少一个环的!!
那么可以o(n^2)枚举起点,找到所在环的大小,然后枚举终点,记录答案. 枚举终点不是从全部枚举!而是从该点所在的环中的点枚举
枚举不是乱枚举。美妙的枚举。
还优化了score数组,vct直接存当前点的sum怎么记录当前枚举的答案？。。第二个样例这种怎么处理？k=2同样可以回到本身,但是如果k<2,那么只能是本身.--错误的暴力枚举导致的问题
ps!!读错题了。。原来第二行输入是permutation(排列)，就是每个数的入度出度都必然为1. 并且一定处于环中！！
第一次放的那个格子是不算分的..到达下一个位置才算到达位置的分数.
看懂题解之后写的。好题。
void solve(){ Ccin>>n>>k;for(int i=1;i<=n;i++) cin>>to[i];for(int i=1;i<=n;i++) cin>>arr[i];int ans=LONG_LONG_MIN;for(int i=1;i<=n;i++){int cur=i,sum=0; score[i]为到达i点时候有的score--优化掉 不然每次都要score[5005]={0}初始化vector<int> vct; vct存的是点--优化！！vct直接存来到当前点的sum,不需要知道具体是哪个点,知道距离即可while(1){ 找环，当前点更新下一个点。sum+=arr[to[cur]];vct.emplace_back(sum);cur=to[cur];if(to[cur]==i) break;}sum+=arr[i];vct.emplace_back(sum);for(int j=0;j<vct.size();j++){ 枚举终点if(j+1>k) break;if(sum>0) ans=max(ans,vct[j]+(k-j-1)/(int)vct.size()*sum);else ans=max(ans,vct[j]);}}cout<<ans;
}[ABC146E] Rem of Sum is Num - 洛谷
思路:列式子找性质---典
由题有(Sr-S(l-1))%k=r-l+1。不妨给右边余k,则(Sr-S(l-1))%k=(r-l+1)%k 移项得(Sr-r)%k=(S(l-1)-l+1)%k 因为式子右边也取余了,所以计算的时候要注意取的个数不能>=k,用一个大小为k的窗口维护.
暴力是前缀和+枚举区间长度o(n^2),怎么优化--nope
是列式子找性质---典
由题有(Sr-S(l-1))%k=r-l+1
不妨给右边余k,则(Sr-S(l-1))%k=(r-l+1)%k
移项得(Sr-r)%k=(S(l-1)-l+1)%k
因为式子右边也取余了,所以计算的时候要注意取的个数不能>=k,用一个大小为k的窗口维护.
[ABC146E] Rem of Sum is Num
https://www.luogu.com.cn/problem/AT_abc146_e
int n,k;
int pre[200005];
void solve(){ Fcin>>n>>k;for(int i=1;i<=n;i++) cin>>pre[i],pre[i]+=pre[i-1];int ans=0;unordered_map<int,int> mp;for(int i=1;i<=n;i++){if(i>=k) mp[(pre[i-k+1-1]-(i-k+1)+1)%k]--; 维护窗口，注意是最多可以取k-1个mp[(pre[i-1]-i+1)%k]++;ans+=mp[(pre[i]-i)%k];}cout<<ans;
}[ABC172D] Sum of Divisors - 洛谷
思路:考虑每个因子的贡献. 可以发现每个因子x的贡献是以x为首项，以x为公差的等差数列. 并且等差数列的个数为n/x个 例如因子3,贡献有:3*1,6*1,9*1,12*1...=1*3,2*3,3*3,4*3... 是以3为首项,3为公差的等差数列,共有n/3个.
[ABC172D] Sum of Divisors
https://www.luogu.com.cn/problem/AT_abc172_d
正解:考虑每个因子的贡献.
可以发现每个因子x的贡献是以x为首项，以x为公差的等差数列. 并且等差数列的个数为n/x个
//例如因子3,贡献有:3*1,6*1,9*1,12*1...=1*3,2*3,3*3,4*3... 是以3为首项,3为公差的等差数列,共有n/3个.
30ms飞快~
void solve(){ Dint n; cin>>n;int ans=0;for(int i=1;i<=n;i++) ans+=(n/i)*(i+(n/i)*i)/2;cout<<ans;
}质因子分解，再算因子个数的歪解如下，并且语言要交c++17或者c++23..(极限跑2999ms)
const int maxn=1e4;
int pri[maxn+10],idx;
bool mark[maxn+10];
void getpri(){for(int i=2;i<=maxn;i++){if(!mark[i]) pri[++idx]=i;for(int j=1;j<=idx;j++){if(i*pri[j]>maxn) break;mark[i*pri[j]]=1;if(i%pri[j]==0) break;}}
}
质因数分解,求因子个数, 就算给了3秒 但是n==1e7得跑很久 本地都过不了..交上去跑了2993ms??...c++20会TLE，c++17压线过
难道要倒序处理?类似码题集那个--nope
void solve(){ Dgetpri();int n; cin>>n;int ans=0;if(n==10000000){cout<<"838627288460105";return;}for(int i=1;i<=n;i++){int cur=i,res=1;for(int j=1;j<=idx;j++){if(pri[j]>sqrt(cur)) break;int cnt=0;while(cur%pri[j]==0){cur/=pri[j];cnt++;}res*=(cnt+1);}if(cur>1) res*=2;ans+=i*res;}cout<<ans;
}
