1. 云图网首页
  2. 技术专区
  3. 编程笔记

训练记录

• 编程笔记


————恢复内容开始————

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);
}

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/281324.html

赞 (0)
0
上一篇 2022年8月21日
下一篇 2022年8月21日

相关推荐

发表回复

登录后才能评论