训练记录

本文主要是介绍训练记录，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

------------恢复内容开始------------

D - Together Square

这道题很有意思吧！打表去OEIS查查到一串天文最后还是想了一下性质平方数是不是分解质因数都是偶的那我们记录质因数奇数的就好了然后奇数的可以和奇数的拼一起就是偶数的了并且我们枚举每一个都是全排列

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 1<<10;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int fun(int n){
    int res=1;
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int cnt=0;
            while(n%i==0){
                n/=i;
                cnt++;
            }
            if(cnt%2){
                res*=i;
            }
        }
    }
    if(n>1)res*=n;
    return res;
}
void solve() {
    int n;cin>>n;
    map<int,int>mp;
    for(int i=1;i<=n;i++){
        int t=fun(i);
        mp[t]++;
    }
    int ans=0;
    for(auto p:mp)ans+=p.second*p.second;
    cout<<ans<<endl;
}
signed main(){
    fast
    solve();
    return ~~(0^_^0);
}

D. Chip Move

其实有时候直觉挺重要的我好像知道是个dp 却无从下手打表看了下发现也没啥思路咋办？？？
其实更重要的是相信自己的直觉我们就比如他是个dp 然后我们咋设计状态由题意得我们一维要表示步数一维要表示当前在第几个位置（其实这里我们很容易想到刷表的方式去暴力枚举正难则反嘛我们可以递推的去让他做道线性复杂度因为我们都是有顺序的希望自己下次能反应过来www
而且 k+1 必须由 k 转移过来那我们的f[i][j]就表示在第i（从k开始枚举）步我们在第j个位置的cnt
但是这是n2的咋办？？？我们仔细想一下好像是有上届的是吧我们最坏k=1开始 1+2+3+4+5+...+t=n 那我们t也只是个根号级别的
所以时间复杂度是根号n*n的
好我们继续想状态计算：f[i][j]=f[i-1][j-i]+f[i][j-i] 好像这样确实做到不重不漏了
最后我们再用个滚动数组优化即可记住我们是要求每一个位置的cnt 所以每一步都要加上去初始化就是f[k]=1;
其实转念一想这应该抽象成一个完全背包我们每次都可以拿无限个i进去（如果能观察出这一点的 dp 和状态转移都很一眼了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);

void solve() {
    int n,k;cin>>n>>k;
    vector<int>b(n+10),ans(n+10),f(n+10);
    f[k]=1;
    int nw=k;
    for(int i=k;nw<=n;i++){
        for(int j=i;j<=n;j++){
            f[j]=(f[j]+b[j-i]+f[j-i])%mod;
        }
        nw+=i;
        b=f;
        for(int j=1;j<=n;j++){
            ans[j]=(ans[j]+f[j])%mod;
            f[j]=0;
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
}
signed main(){
    fast
    solve();
    return ~~(0^_^0);
}

D. Required Length

我也是第一次真见到搜索题我看了一眼范围感觉每层最坏只要80层然后分支也最多就10 感觉数据范围是可做的
然后随便写了一个T了
最后想了一下一个预见性的剪枝就是我们最多每一次+1位我们当前位贪心每次都加1位再与res比较即可
后面看了题解有IDA* 感觉也是很正确的启发式函数就是n-当前位哦原来就是和我这个剪枝一样啊！

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,x,res=inf;
void dfs(int m,int ans){
    if(ans>=res)return;
    vector<int>v;
    int cnt=m;
    while(cnt)v.push_back(cnt%10),cnt/=10;
    if(n-v.size()+ans>=res)return;
    if(v.size()==n){
        res=min(res,ans);
    }
    int flag1=0;
    for(auto i:v)if(i!=1&&i!=0)flag1=1;
    if(!flag1)return;
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=v.size()-1;i>=0;i--){
        dfs(m*v[i],ans+1);
    }
}
void solve() {
    cin>>n>>x;
    dfs(x,0);
    if(res==inf)cout<<-1<<endl;
    else cout<<res<<endl;
}
signed main(){
    fast
    //int T;cin>>T;
    //while(T--) {
        solve();
   // }
    return ~~(0^_^0);
}

CF1661B Getting Zero

警惕记忆化搜索不能有%操作不然会成环警惕CF不能打表
观察出来了每次<<1 所以最多15次但是有加法咋办感觉想了几个情况还是挺麻烦的不如暴力吧算算O（N1515）才3百万那没事了那没事了 //今天居然solved2

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 32768;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int lowbit(int x){return x&-x;}
void solve() {
    int n;cin>>n;
    int res=inf;
    for(int j=0;j<=15;j++) {
        int t=lowbit(n+j);
        if(t>=1<<15||!t){res=min(res,j);continue;}
        for (int i = 0; i < 15; i++) {
            if (t >> i & 1)res=min(res,15-i+j);
        }
    }
    cout<<res<<' ';
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

G. Count the Trains

我们知道这个是肯定是单调递减的所以可以用二分
我们先预处理好每个火车头的编号放进一个set里面正好set也是单调的
然后我们对于每次更新就是看其能不能小于他的火车头要是能小于他将自成一个火车头并且还会改变后面的火车头
咋做呢？？？
暴力的话好像是可以的因为我们最多本来就有n个头插入m个那删除不可能删>n+m 所以暴力也是O（nlog）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 32768;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    set<int> s;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        if (s.empty())s.insert(i);
        else if(a[*s.rbegin()] > a[i])s.insert(i);
    }
    while (m--) {
        int j, c;
        cin >> j >> c;
        a[j] -= c;
        auto it = s.upper_bound(j);
        if (it != s.begin()) {
            it = prev(it);
            if (a[*it] > a[j])s.insert(j);
        }
        while (1) {
            it = s.upper_bound(j);
            if (it != s.end() && a[*it] >= a[j])s.erase(it);
            else break;
        }
        cout << (int) s.size() << ' ';
    }
    cout << endl;
}
signed main(){
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

CF1690E Price Maximization

很容易发现这是%后再贪心就是了但是我最开始写的一个t了应该是我拿l来贪复杂度高了
那我们可以拿高位来贪只要满足r的l 然后就可以一只往后走只用扫一遍最后记得处处判l<r
要是拿l来贪就要考虑先从k-l 开始扫感觉常数有点大！

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 32768;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
void solve() {
    int n,k,ans=0;cin>>n>>k;
    vector<int>a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        ans+=a[i]/k;
        b[i]=a[i]%k;
    }
    sort(b.begin(),b.end());
    int l=0,r=n-1;
    while(l<r){
        while(b[l]+b[r]<k&&l<r)l++;
        if(b[l]+b[r]>=k&&l<r)ans++,l++,r--;
        else break;
    }
    cout<<ans<<endl;
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

F. Shifting String

对于每个置换我们可以将其分成很多个环以往环都是确定的数但这道题不同的是有了字母那我们就可以用链表模拟这个置换因为我们每次置换不会超过n 时间复杂度最坏的O（n2）的
当模拟的now==pre就直接和求一次lcm就行了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 32768;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int p[N],n,vis[N];
string s;
vector<int>c;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void dfs(int u){
    if(vis[u])return;
    vis[u]=1;
    c.push_back(u);
    dfs(p[u]);
}
void solve() {
    cin>>n>>s;s=")"+s;
    for(int i=1;i<=n;i++)cin>>p[i],vis[i]=0;
    int ans=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            c.clear();
            dfs(i);
            list<char>pre,now;
            for(auto id:c)pre.push_back(s[id]);
            now=pre;
            now.push_back(now.front());now.pop_front();
            int res=1;
            while(pre!=now){
                now.push_back(now.front());now.pop_front();
                res++;
            }
            ans=lcm(ans,res);
        }
    }
    cout<<ans<<endl;
}
signed main(){
    fast
    int T;cin>>T;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

这篇关于训练记录的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

训练记录

D - Together Square

D. Chip Move

D. Required Length

CF1661B Getting Zero

G. Count the Trains

CF1690E Price Maximization

F. Shifting String

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯