• Codeforces Round 895 (Div. 3)

    Codeforces Round 895 (Div. 3)

    A. Two Vessels

    思路：
    我们可以发现当在 a 拿 c 到 b 其实可以让他们差值减少 2c，所以对a和b的差值除以2c向上取整即可

    #include
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define x first
#define y second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pairpii;
int n,m,k,Q,cnt,t;
vectordel;
int a[200010],b[200010];
int prime[N];
bool st[N];
mapmp;
void solve(){
    int a,b,c;cin>>a>>b>>c;
    int x=abs(a-b);
    int y=x/(2*c);
    if(x%(2*c))y++;
    cout<>t;
    while(t--)solve();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    B. The Corridor or There and Back Again

    思路：
    我们可以发现我们当前能到达最远是 d+（s-1）/ 2，然后就是找这些里面最小的值即可

    #include
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define x first
#define y second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pairpii;
int n,m,k,Q,cnt,t;
vectordel;
int a[200010],b[200010];
int prime[N];
bool st[N];
mapmp;
void solve(){
    int n;cin>>n;
	int a,b;
	int ans=10000000000;
	rep(i,0,n-1){
		cin>>a>>b;
		ans=min(ans,a+(b-1)/2);
	}
	cout<>t;
    while(t--)solve();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    C. Non-coprime Split

    思路：
    这里我们分三种情况：
    ① 如果a ！= b，我们就能找一个偶数，输出2和偶数-2
    ② 如果a== b，如果a和b不是质素那么就直接找出他的最小的约数即可
    ③ 如果a ==b，如果a和b是质素那么就输出-1
    还有些细节注意下就行

    #include
using namespace std;
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define x first
#define y second
const int N=2e6+10,M=2e5;
typedef double db;
typedef pairpii;
int n,m,k,Q,cnt,t;
vectordel;
int a[200010],b[200010];
int prime[N];
bool st[N];
mapmp;
bool isPrime(int n)
{
	if (n <= 3)//当n不大于3时只有1不是素数
		return n > 1;
	if (n % 6 != 1 && n % 6 != 5)//只有6i+1和6i+5可能是素数
		return false;
	for (int i = 5; i <= sqrt(n); i += 6)
	{
		if (n % i == 0 || n % (i + 2) == 0)
			return false;
	}
	return true;
}
void solve(){
    int a,b;cin>>a>>b;
    if(a==b&&a<=2){
        cout<<-1<>t;
    while(t--)solve();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    D. Plus Minus Permutation

    思路：
    我们可以发现如果某个数能被x和y同时整除的话对答案没有贡献，所以，我们只需要找到在x中的数不在y中的个数num1，在y中的数不在x中的数num2，然后根据前n项和公式sum1-sum2即可

    #include
using namespace std;
#define int long long
signed main(){
    int t;
    cin>>t;
    while(t--){
    int n,x,y;cin>>n>>x>>y;
    int d=__gcd(x,y);
	d=x/d*y;
	int c=n/d;
	x=n/x-c;
	y=n/y-c;
	cout<
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    E. Data Structures Fan

    思路1：线段树
    没补
    思路2：异或性质
    在这里插入图片描述

    #include 
using namespace std;
typedef long long LL;
typedef pair pii;
void solve()
{
    int n; cin >> n;
    vector a(n + 10),sum(n+10);
    for (int i = 1; i <= n; i++) cin >> a[i],sum[i]=sum[i-1]^a[i];
    string op; cin >> op;
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < n; i++)
    {
        if (op[i] == '0') sum2 ^= a[i + 1];
        else sum1 ^= a[i + 1];
    }
    //cout<<"sum== "<> q;
    while (q--)
    {
        int cnt;
        cin >> cnt;
        if (cnt == 2)
        {
            int x; cin >> x;
            if (x == 0) cout << sum2 << ' ';
            else cout << sum1 <<' ';
        }
        else
        {
            int l, r; cin >> l >> r;
            sum1 ^= sum[r] ^ sum[l - 1];
            sum2 ^= sum[r] ^ sum[l - 1];
        }
    }
    cout<> t;
    while (t--)
        solve();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    F. Selling a Menagerie

    思路：
    在这里插入图片描述

    #include 
using namespace std;
typedef long long LL;
typedef pair pii;
const int N = 1e5 + 10;
int a[N], c[N];
int d[N], minn = 1e9 + 10, id = -1;
bool st[N];
void dfs(int u)
{
    if (st[u]) return;
    st[u] = true;
    int j = a[u];
    if (minn > c[j]) minn = c[j], id = j;
    dfs(j);
}
void solve()
{
    queue q;
    vector ans;
    int n; cin >> n;
    for (int i = 0; i <= n; i++) st[i] = false, d[i] = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], d[a[i]]++;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q.push(i);
    while (q.size())
    {
        int t = q.front();
        ans.push_back(t);
        st[t] = true;
        q.pop();
        if (--d[a[t]] == 0) q.push(a[t]);
    }
    for (int i = 1; i <= n; i++)
        if (!st[i])
        {
            minn = c[i];
            id = i;
            dfs(i);//找最小的贡献
            int x = a[id];
            do
            {
                ans.push_back(x);
                x = a[x];
            } while (x != a[id]);
        }
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
    cout << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t; cin >> t;
    while (t--)
        solve();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    G. Replace With Product

    思路：
    在这里插入图片描述

    #include 
using namespace std;
#define int long long
// const int N = 1e5 + 10;

const int N = 2e5 + 10, M = 4e5 + 10;

int n, a[N], b[N], idx;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int l = 1, r = n;
    while (a[l] == 1 && l < r)
        l++;
    while (a[r] == 1 && l < r)
        r--;
    int res = 1;
    for (int i = l; i <= r; ++i)
    {
        res *= a[i];
        if (res > 1e9)
        {
            cout << l << " " << r << "\n";
            return;
        }
    }

    idx = 0;
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] > 1)
            b[++idx] = i;
        sum += a[i];
    }
    int ans = sum, ansl = 1, ansr = 1;
    for (int i = 1; i <= idx; ++i)
    {
        res = 1;
        l = b[i];
        int s = 0;
        for (int j = i; j <= idx; ++j)
        {
            res *= a[b[j]];
            r = b[j];
            s += a[b[j]];
            int val = sum - s - (r - l + 1 - (j - i + 1)) + res;
            if (val > ans)
            {
                ans = val;
                ansl = l, ansr = r;
            }
        }
    }
    cout << ansl << " " << ansr << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t; cin >> t;
    while (t--)
        solve();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
  • 相关阅读:
    使用VUE3.0版本搭建H5模板
    java如何使用正则表达式剔除字符串所有html标签呢？
    快速搭建React TypeScript项目
    工业镜头的重要参数之视场、放大倍率、芯片尺寸--51camera
    产品经理基础--07用户端产品设计
    集成2.5G/5G/10G高速率网络变压器的RJ45网口连接器产品特点介绍
    游戏设计模式专栏(十三）：在Cocos游戏开发中运用责任链模式
    基于LSTM encoder-decoder模型实现英文转中文的翻译机器
    c++图像腐蚀操作
    寒假训练——第三周（背包DP）
  • 原文地址：https://blog.csdn.net/qq_64289808/article/details/132774002