您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

Codeforces Round #708 (Div. 2)(BCDE1)

B. M-arrays

题目大意:n个数字,求最小划分,使得每组数里相邻的两个数的和能被m整除

思路:将每个数对m取模,然后i和(m-i)的数分在一组,多的数单独放在一组

(太妙了,取模这个操作第一次想不到)

C. k-LCM

题目大意:给定n和k,构造一串数,使得和为n,且所有数的lcm <= n/2。

思路:先看c1,三个数的话,又要让lcm不超过n/2,那最大数肯定不能超过n/2,容易想到n为4的倍数时,我们可以构造(n/2,n/4,n/4)。接下来去看n%4==1,2,3时的情况。

n%4==1,(n/2,n/2,1)

n%4==2,(n/2,n/2,2)

n%4==3,(1+n/2,1+n/2,1)

于是就可以做了。

再看c2,和c1不同的是k不是三,既然都是c,不妨往c1的思路去靠。因为n>=k,我们去构造3个数的情况,其他数都赋值为1,问题就转化成c1了

D. Genius

题目大意:n个数各自有tag值和s值,当当前分数<|ci-cj|时,可以从i到j,或者j到i,然后获得|si-sj|的分数,其中ci = 2^i,起点任意选。求最大得分

思路:dp

仔细想一下,其实ci是个迷惑操作,i到j有两种转移方法,假设i上一步在k点。

当j在i左边时,有|i-k| < |i-j|(下标距离)

当j在i右边时,有|i-k|<|i-j|或者 k  < i

 我们外层枚举点从左跳到右的情况(i->i+x),内层枚举i+x -> j( j < i+x)的情况,dp[i]表示i点得到的最大分数。注意内循环应该递减,因为右跳到左步数应该递增地去更新

同时更新两个点

dp[i] = max(dp[j] + abs(s[i]-s[j])) 

dp[j] = max(dp[i] + abs(s[i]-s[j])) 

#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <deque>
using namespace std;
typedef long long ll;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define scd(v) scanf("%d",&v)
#define scdd(a,b) scanf("%d %d",&a,&b)
#define endl "\n"
#define IOS ios::sync_with_stdio(false)
#define pb push_back
#define all(v) v.begin(),v.end()
#define mst(v,a) memset(v,a,sizeof(v))
#define ls p<<1
#define rs p<<1|1
#define int long long 
const int N=5000+10;
int n,k;
int tag[N],s[N];
int dp[N];
void solve()
{
    mst(dp,0);
    _for(i,2,n)
    {
        //步数递增,j应该倒着循环
        _rep(j,i-1,1)
        {
            if( tag[j] == tag[i])  continue;
            int dpi = dp[i] , dpj = dp[j];
            dp[i] = max(dp[i] , dpj + abs(s[j] - s[i]));
            dp[j] = max(dp[j] , dpi + abs(s[j] - s[i]));


        }
    }
    int ans=0;
    _for(i,1,n ) ans = max( ans , dp[i]);
    cout<<ans<<endl;
}
signed main()
{
    //!!
//    freopen("data.txt","r",stdin);
//    !!
    IOS;
    int T;cin>>T;
    while( T-- )
    {
        cin>>n;
        _for(i,1,n) cin>>tag[i];
        _for(i,1,n) cin>>s[i];
        solve();
    }
}

E1. Square-free division (easy version)

题目大意:给定n个数,求最小划分,使得每组里面任意两个数的成绩不是完全平方

思路:数的分解,素数筛

暴力n方铁tle

如何快速判断一个数是否和前面任意一个数的乘积为完全平方?我们知道一个数的质因子的次方如果都为偶数则为完全平方数,两个数相乘的话同理看质因子次数的奇偶。也就是说一个数的某质因子如果为偶次方的话其实是不影响的,可以直接去掉,比如判断8*2, 8 = 2*2*2可以去掉两个2,等价于判断2*2,两个质因子2,说明为完全平方数。

有了这个思路后就可以做,先素数筛(只要筛根号n的数即可,不然tle了),然后预处理每个数删掉它的所有偶数次方的质因子,然后扫一遍输入数组,当出现两个同样的数(即质因子完全相同)时,情况之前的记录——用map记录,然后组数++

O(nlogn)

#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <deque>
using namespace std;
typedef long long ll;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define scd(v) scanf("%d",&v)
#define scdd(a,b) scanf("%d %d",&a,&b)
#define endl "\n"
#define IOS ios::sync_with_stdio(false)
#define pb push_back
#define all(v) v.begin(),v.end()
#define mst(v,a) memset(v,a,sizeof(v))
#define ls p<<1
#define rs p<<1|1
#define int long long
const int N=2e5+10;
int n,k;
int a[N];
int v[N],prim[449],tot;
map<int ,int > mp;
void getprim(int n)
{
    _for(i,2,n)
    {
        if( !v[i] )
        {
            prim[++tot]=i;
        }
        _for(j,1,tot)
        {
            if( i*prim[j] > n ) break;
            v[i*prim[j]]=1;
            if( i%prim[j]==0 ) break;
        }
    }
}
void solve()
{
    mp.clear();
    //分解
    _for(i,1,n)
    {
        cin>>a[i];
        _for(j,1,tot)
        {
            if( a[i]<2 ) break;
            if( a[i]%prim[j] == 0 )
            {
                while( a[i]%(prim[j] *prim[j]) == 0  ) a[i]/=prim[j]*prim[j];
            }
        }
    }
    int ans=0;
    _for(i,1,n)
    {
        if( mp[a[i]])
        {
            ans++;
            mp.clear();
        }
        mp[a[i]]=1;
    }
    cout<<ans+1<<endl;
}
signed main()
{
    //!!
//    freopen("data.txt","r",stdin);
//    !!
    IOS;
    getprim(3168);
    int T;cin>>T;
    while( T-- )
    {
        cin>>n>>k;
        solve();
    }
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进