[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; init
for(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(){ C
cin>>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(){ F
cin>>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(){ D
int 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(){ D
getpri();
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;
}