Codeforces Round #828 (Div. 3)「A暴力」「B小模拟」「C二分」「D预处理+贪心」「E1枚举」 「E2大数质因数分解+dfs求因子」
admin
|
|
246
|
Codeforces

1327 字
|
30 分钟

Codeforces Round #828 (Div. 3)

Number Replacement

题目描述：

长度为n的数组a，每次可以选择所有相同的数字并把他变成同一个任意的字符，进行若干次操作后得到的数组b,现在给你a和b数组，问是否存在一种方式使得a能变成b

思路：

暴力for循环判断，当a[i]=a[j]时，如果b[i]!=b[j]则输出No，全部都判断完了还没有No，则输出Yes

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    cin >> s;
    s = " " + s;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(tr[i] == tr[j]){
                if(s[i] != s[j]){
                    cout << "NO\n";
                    return;
                }
            }
        }
    }
    cout << "YES\n";
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

B. Even-Odd Increments

题目描述：

给定长度为n的数组a，进行q次操作

  • 0 x，则给数组中所有偶数的数字加上x
  • 1 x，则给数组中所有奇数的数字加上x

思路：

用两个变量分别统计奇数和偶数的数量，再用两个变量统计偶数的数字和、奇数的数字和

然后简单讨论一下就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m, k, op, x;
ll tr[MAX];

void work(){
    cin >> n >> m;
    ll odd = 0, even = 0;
    ll num1=0, num2=0;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        if(tr[i] % 2){
            odd += tr[i];
            ++num1;
        }
        else {
            even += tr[i];
            ++num2;
        }
    }
    for(int i = 1; i <= m; ++i){
        cin >> op >> x;
        if(op == 0){//偶数
            if(x % 2 == 0){//x偶数
                even += x * num2;
            }
            else{//x奇数
                even += x * num2;
                odd += even;
                num1 += num2;
                num2 = 0;
                even = 0;
            }
        }
        else{//奇数
            if(x%2==0){
                odd += x * num1;
            }
            else{
                odd += x * num1;
                even += odd;
                num2 += num1;
                odd = 0;
                num1 = 0;
            }
        }
        cout << odd + even << endl;
    }
   
}

int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

C. Traffic Light

题目描述：

给定一个循环播放的红绿灯标识字段s，红绿灯一秒变一个颜色，只有三种颜色，红绿黄，现在给出你所在时刻的红绿灯的颜色p，但是你并不知道你所处的具体时间点，求从任意一个颜色是p的点出发后最多经过t秒一定能遇到一个绿灯，求最小的t

思路：

开二倍长度的数组，把s重复一遍，把所有的绿灯的位置放进数组中，然后枚举每个颜色是p的位置，二分找下一个绿灯，求一下时间的最大值即可 

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n;
char p;
char tr[MAX];
void work(){
    cin >> n >> p;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        tr[i + n] = tr[i];
    }
    if(p == 'g')cout << 0 << endl;
    else{
        vector<int>v;
        for(int i = 1; i <= 2*n; ++i){
            if(tr[i] == 'g')v.push_back(i);
        }
        int ans = 0;
        for(int i = 1; i <= n; ++i){
            if(tr[i] == p){
                int p = lower_bound(v.begin(), v.end(), i)-v.begin();
                ans = max(ans, v[p]-i);
            }
        }
        cout << ans << endl;
    }
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

D. Divisibility by 2^n

题目描述：

长度为n的数组，你要进行若干次操作后，使得 是 的倍数，操作是可以选择一个i,使得a[i]=i*a[i] ,不可以选择之前被操作过的i，问最小进行多少次操作可以满足条件，如果无论如何都不能则输出-1

思路：

预处理出来1到200000能整除2的次数num[i]

计算出每个a[i]能整除2的次数，求和，把前n个num[i]从大到小排序，然后计算就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op, x;
int num[MAX];
int tr[MAX];

int cal(int x){
    int num = 0;
    while(x % 2 == 0){
        ++num;
        x/=2;
    }
    return num;
}

void work(){
    cin >> n;
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        cnt += cal(x);
    }
    if(cnt >= n){
        cout << 0 << endl;
        return;
    }
    else{
        vector<int>v;
        for(int i = 1; i <= n; ++i){
            v.push_back(num[i]);
        }
        sort(v.begin(), v.end(),greater<int>());
        for(int i = 0; i < v.size(); ++i){
            cnt += v[i];
            if(cnt >= n){
                cout << i + 1 << endl;
                return;
            }
        }
        cout << -1 << endl;
    }
    
}
int main(){
    io;
    for(int i = 1; i <= 200000; ++i){
        num[i] = cal(i);
    }
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

E1. Divisible Numbers (easy version)

题目描述：

给定(a,b),(c,d)，代表矩阵左上角、右下角，你需要在(a+1,b+1)到(c,d)的矩形里面找一个点(x,y),满足x*y是a*b的倍数

思路：

简单版本的范围只有1e5，我们可以直接枚举x，看看在(b,d+1)里面找a*b/gcd(a*b,x),这个可以直接O(1)判断

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op, x;
int num[MAX];
int tr[MAX];

int cal(int x){
    int num = 0;
    while(x % 2 == 0){
        ++num;
        x/=2;
    }
    return num;
}

void work(){
    cin >> n;
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        cnt += cal(x);
    }
    if(cnt >= n){
        cout << 0 << endl;
        return;
    }
    else{
        vector<int>v;
        for(int i = 1; i <= n; ++i){
            v.push_back(num[i]);
        }
        sort(v.begin(), v.end(),greater<int>());
        for(int i = 0; i < v.size(); ++i){
            cnt += v[i];
            if(cnt >= n){
                cout << i + 1 << endl;
                return;
            }
        }
        cout << -1 << endl;
    }
}

int main(){
    io;
    for(int i = 1; i <= 200000; ++i){
        num[i] = cal(i);
    }
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

E2. Divisible Numbers (hard version)

题目描述：

跟上一个题一样，只不过数据范围变成了1e9

思路：

我们分解出a*b的所有的因子，然后枚举因子为x，我们假设由行来提供x的倍数，由列来提供y的倍数，则只需要判断(a+1, c)中是否存在x的倍数，再判断(b+1,d)中是否存在a*b/x的倍数即可

用Pollard_Rho算法进行因数分解，再用dfs进行爆搜，即可得到所有因子个数，然后再利用上面的方法去判断计算一下就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
const int N = 5e6 + 7;
#define  int long long
#define MAX 5000000 + 50
ll a, b, c, d, n, m;

int tr[MAX];
ll x, y;
struct BigIntegerFactor {
    const static int N = 5e6 + 7;
    ll prime[N], p[N], fac[N], sz, cnt; //多组输入注意初始化cnt = 0
    inline ll mul(ll a, ll b, ll mod) {          //WA了尝试改为__int128或慢速乘
        if (mod <= 1000000000)
            return a * b % mod;
        return (a * b - (ll)((long double)a / mod * b + 1e-8) * mod + mod) % mod;
    }
    void init(int maxn) {
        int tot = 0;
        sz = maxn - 1;
        for (int i = 1; i <= sz; ++i)
            p[i] = i;
        for (int i = 2; i <= sz; ++i) {
            if (p[i] == i)
                prime[tot++] = i;
            for (int j = 0; j < tot && 1ll * i * prime[j] <= sz; ++j) {
                p[i * prime[j]] = prime[j];
                if (i % prime[j] == 0)
                    break;
            }
        }
    }
    ll qpow(ll a, ll x, ll mod) {
        ll res = 1ll;
        while (x) {
            if (x & 1)
                res = mul(res, a, mod);
            a = mul(a, a, mod);
            x >>= 1;
        }
        return res;
    }
    bool check(ll a, ll n) {                     //二次探测原理检验n
        ll t = 0, u = n - 1;
        while (!(u & 1))
            t++, u >>= 1;
        ll x = qpow(a, u, n), xx = 0;
        while (t--) {
            xx = mul(x, x, n);
            if (xx == 1 && x != 1 && x != n - 1)
                return false;
            x = xx;
        }
        return xx == 1;
    }
    bool miller(ll n, int k) {
        if (n == 2)
            return true;
        if (n < 2 || !(n & 1))
            return false;
        if (n <= sz)
            return p[n] == n;
        for (int i = 0; i <= k; ++i) {            //测试k次
            if (!check(rand() % (n - 1) + 1, n))
                return false;
        }
        return true;
    }
    inline ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    inline ll Abs(ll x) {
        return x < 0 ? -x : x;
    }
    ll Pollard_rho(ll n) {                 //基于路径倍增的Pollard_Rho算法
        ll s = 0, t = 0, c = rand() % (n - 1) + 1, v = 1, ed = 1;
        while (1) {
            for (int i = 1; i <= ed; ++i) {
                t = (mul(t, t, n) + c) % n;
                v = mul(v, Abs(t - s), n);
                if (i % 127 == 0) {
                    ll d = gcd(v, n);
                    if (d > 1)
                        return d;
                }
            }
            ll d = gcd(v, n);
            
            if (d > 1)
                return d;
            s = t;
            v = 1;
            ed <<= 1;
        }
    }
    void getfactor(ll n) {                         //得到所有的质因子(可能有重复的)
        if (n <= sz) {
            while (n != 1)
                fac[cnt ++ ] = p[n], n /= p[n];
            //            max_factor = max_factor > p[n] ? max_factor : p[n];
            return;
        }
        if (miller(n, 6)) {
            fac[cnt ++ ] = n;
            //            max_factor = max_factor > n ? max_factor : n;
        }
        else {
            ll d = n;
            while (d >= n)
                d = Pollard_rho(n);
            getfactor(d);
            getfactor(n / d);
        }
        return ;
    }
} Q;

ll yinzi[10005];
ll num[10005];

ll mul;
vector<ll>fuck;
ll cao(ll a, ll b){
    ll c = 1;
    while(b--)c*=a;
    return c;
}
void dfs(int id){
    if(id == m+1){
        fuck.push_back(mul);
        return;
    }
    for(int i = 0; i <= num[id]; ++i){
        mul = mul * 1ll * cao(yinzi[id], i);
        dfs(id + 1);
        mul = mul / (1ll * cao(yinzi[id], i));
    }
}

ll cal(ll l, ll r, ll p){
//    cout << l << ' ' << r << ' ' << p << endl;
    ll ans = (l / p) * p;
    if(ans>=l&&ans<=r)return ans;
    ans += p;
    if(ans>=l&&ans<=r)return ans;
    else return -1;
}

void work(){
    cin >> a >> b >> c >> d;
    Q.cnt = 0;
    n = a * b;
    if(n == 1){
        cout << c << ' ' << d << endl;
        return;
    }
    Q.getfactor(n);
    map<ll, ll>mp;
    for(int i = 0; i < Q.cnt; ++i){
        ++mp[Q.fac[i]];
    }
    m = 0;
    for(auto [x,y]:mp){
        yinzi[++m] = x;
        num[m] = y;
    }
    mul = 1ll;
    fuck.clear();
    dfs(1);
    sort(fuck.begin(), fuck.end(), greater<ll>());
//    for(auto x : fuck)cout << x << ' ';
    
    for(auto x : fuck){
        if(x == 0)continue;
        if(cal(a+1, c, x) != -1 && cal(b+1, d, n/x) != -1){
            cout << cal(a+1, c, x) << ' ' << cal(b+1, d, n/x) << endl;
            return;
        }
    }
    cout << -1 << ' ' << -1 << endl;
}


signed main(){
    int t;cin>>t;while(t--)
    work();
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
cf
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Codeforces Round 729 (Div. 2) C. Strange Function「思维 + 数论」

							
							

							
Codeforces Round #719 (Div. 3)

							
							

							
Educational Codeforces Round 138 (Rated for Div. 2) 「D逆向思维 递推」

							
							

							
Educational Codeforces Round 115 (Rated for Div. 2) D. Training Session

							
							

							
Codeforces Round #737 (Div. 2)