首页 > 编程语言 >Codeforces Round 918 (Div. 4) （前缀和，权值树状数组，二维偏序, python + golang）

Codeforces Round 918 (Div. 4) （前缀和，权值树状数组，二维偏序, python + golang）

时间：2023-12-30 22:11:53浏览次数：40  
标签：偏序 return python fmt Codeforces int range int64 func

Dashboard - Codeforces Round 918 (Div. 4) - Codeforces

 

 

from collections import *


def solve():
    a, b, c = list(map(int, input().split()))
    hs = defaultdict(int)
    hs[a] += 1
    hs[b] += 1
    hs[c] += 1

    for i in hs:
        if hs[i] == 1:
            print(i)
            break


T = int(input())

for i in range(T):
    solve()
package main

import (
    "bufio"
    "fmt"
    "os"
)

var in = bufio.NewReader(os.Stdin)

func main() {
    var T int
    fmt.Fscan(in, &T)

    for tt := 0; tt < T; tt++ {
        var a, b, c int
        fmt.Fscan(in, &a, &b, &c)
        mp := make(map[int]int)
        mp[a] += 1
        mp[b] += 1
        mp[c] += 1
        for k, v := range mp {
            if v == 1 {
                fmt.Println(k)
                break
            }
        }
    }
}

 

 

 

from collections import *


def solve():
    g = []
    for i in range(3):
        g.append(input())

    x = 0
    for i in range(3):
        for j in range(3):
            if g[i][j] == '?':
                x = i

    st = set(g[x])
    for i in range(ord('A'), ord('C') + 1):
        if chr(i) not in st:
            print(chr(i))
            break


T = int(input())

for i in range(T):
    solve()
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var in = bufio.NewReader(os.Stdin)

func readLine() []string {
    inp, _ := in.ReadString('\n')
    return strings.Split(strings.Trim(inp, " \r\n"), " ")
}

func stoi(s string) int64 { v, _ := strconv.ParseInt(s, 10, 64); return v }

func main() {
    T := stoi(readLine()[0])

    for tt := 0; tt < int(T); tt++ {
        cnt := make([]int, 3)
        for i := 0; i < 3; i++ {
            str := readLine()[0]
            for _, v := range str {
                if v != '?' {
                    cnt[v-'A']++
                }
            }
        }

        for i, v := range cnt {
            if v == 2 {
                fmt.Println(string(rune('A' + i)))
                break
            }
        }
    }
}

 

 

 这道题就是看所给数组的和能不能分解为平方和

import math
from collections import *


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    s = sum(a)
    ss = int(math.sqrt(s))
    if ss * ss == s:
        print("YES")
    else:
        print("NO")


T = int(input())

for i in range(T):
    solve()
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

var in = bufio.NewReader(os.Stdin)

func readLine() []string {
    ipt, _ := in.ReadString('\n')
    return strings.Split(strings.Trim(ipt, "\r\n"), " ")
}

func stoi(s string) int64 { v, _ := strconv.ParseInt(s, 10, 64); return v }

func main() {
    T := int(stoi(readLine()[0]))

    for tt := 0; tt < T; tt++ {
        readLine()
        var s int64 = 0
        for _, v := range readLine() {
            s += stoi(v)
        }
        sq := sort.Search(1e9, func(i int) bool {
            return int64(i)*int64(i) > s
        }) - 1

        if int64(sq)*int64(sq) == s {
            fmt.Println("YES")
        } else {
            fmt.Println("NO")
        }
    }
    
}

 

 一个小贪心，当我们遇到辅音字母时，它可以作为开头，就看当前位置往后三个位置是不是辅音字母，如果是，则s[i:i + 3]加到答案中（cvc），否则s[i:i+2] (cv)。

import math
from collections import *

ll = ['b', 'c', 'd']


def is_c(ss: str) -> bool:
    return ss in ll


def solve():
    n = int(input())
    s = input()
    res = []
    i = 0
    while i < n - 3:
        if is_c(s[i + 3]):
            res.append(s[i: i + 3])
            res.append('.')
            i += 3
        else:
            res.append(s[i: i + 2])
            res.append('.')
            i += 2
    res.append(s[i:])
    print(''.join(res))


T = int(input())

for i in range(T):
    solve()
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var in = bufio.NewReader(os.Stdin)

func readLine() []string {
    ipt, _ := in.ReadString('\n')
    return strings.Split(strings.Trim(ipt, "\r\n"), " ")
}

func stoi(s string) int64 { v, _ := strconv.ParseInt(s, 10, 64); return v }

func Isc(c rune) bool {
    return c == 'b' || c == 'c' || c == 'd'
}

func main() {
    T := int(stoi(readLine()[0])) // 读一个整数

    for tt := 0; tt < T; tt++ {
        n := int(stoi(readLine()[0]))
        s := readLine()[0]
        ans := []rune{}
        ss := []rune(s)
        i := 0
        for i < n-3 {
            if Isc(rune(s[i+3])) {
                ans = append(ans, ss[i:i+3]...)
                ans = append(ans, '.')
                i += 3
            } else {
                ans = append(ans, ss[i:i+2]...)
                ans = append(ans, '.')
                i += 2
            }
        }

        ans = append(ans, ss[i:]...)
        fmt.Println(string(ans))
    }

}

 

 本题就是看有没有一个连续子数组中，奇数和等于偶数和，经典前缀和+哈希

from collections import *
from itertools import *


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    c = set()
    c.add(0)
    for i in range(len(a)):
        if i % 2 == 0:
            a[i] = -a[i]

    s = 0
    for i in range(n):
        s += a[i]
        if s in c:
            print("YES")
            return
        c.add(s)

    print("NO")


T = int(input())

for i in range(T):
    solve()
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var in = bufio.NewReader(os.Stdin)

func readLine() []string {
    ipt, _ := in.ReadString('\n')
    return strings.Split(strings.Trim(ipt, "\r\n"), " ")
}

func stoi(s string) int64 { v, _ := strconv.ParseInt(s, 10, 64); return v }

func Isc(c rune) bool {
    return c == 'b' || c == 'c' || c == 'd'
}

func solve() {
    var n int
    fmt.Fscan(in, &n)
    a := make([]int64, n)
    for i := range a {
        fmt.Fscan(in, &a[i])
        if i%2 == 0 {
            a[i] = -a[i]
        }
    }

    var s int64 = 0
    mp := make(map[int64]bool)
    mp[0] = true
    for _, x := range a {
        s += x
        if mp[s] {
            fmt.Println("YES")
            return
        }
        mp[s] = true
    }

    fmt.Println("NO")
}

func main() {
    var T int
    fmt.Fscan(in, &T)

    for tt := 0; tt < T; tt++ {
        solve()
    }

}

 

 可将问题抽象为一个二维偏序问题，可以使用排序+权值树状数组解决。

由于数据范围太大，要使用离散化减小数据范围

from itertools import *
from collections import *
import bisect


def lowbit(x: int) -> int:
    return x & -x


def update(nums, x, n):
    while x <= n:
        nums[x] += 1
        x += lowbit(x)


def query(nums, x) -> int:
    res = 0
    while x > 0:
        res += nums[x]
        x -= lowbit(x)
    return res


def solve():
    n = int(input())
    se = []
    b = []
    for _ in range(n):
        x, y = map(int, input().split())
        se.append((x, y))
        b.append(y)

    se.sort(key=lambda x: (x[0], x[1]))
    b.sort()
    num = [0] * (n + 1)
    ans = 0
    for i in range(n - 1, -1, -1):
        idx = bisect.bisect_left(b, se[i][1]) + 1
        ans += query(num, idx)
        update(num, idx, n)

    print(ans)


T = int(input())
for _ in range(T):
    solve()
package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

var in = bufio.NewReader(os.Stdin)

func readLine() []string {
    ipt, _ := in.ReadString('\n')
    return strings.Split(strings.Trim(ipt, "\r\n"), " ")
}

func stoi(s string) int64 { v, _ := strconv.ParseInt(s, 10, 64); return v }

func lowbit(x int64) int64 {
    return x & -x
}

func add(nums []int64, x int64, n int64) {
    for x <= n {
        nums[x] += 1
        x += lowbit(x)
    }
}

func query(nums []int64, x int64) int64 {
    var res int64 = 0
    for x > 0 {
        res += nums[x]
        x -= lowbit(x)
    }
    return res
}

func solve() {
    var n int
    fmt.Fscan(in, &n)
    a := make([][2]int64, n)
    alls := []int64{}
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &a[i][0], &a[i][1])
        alls = append(alls, a[i][1])
    }

    sort.Slice(alls, func(i, j int) bool {
        return alls[i] < alls[j]
    })

    sort.Slice(a, func(i, j int) bool {
        if a[i][0] == a[j][0] {
            return a[i][1] < a[j][1]
        }
        return a[i][0] < a[j][0]
    })

    num := make([]int64, n+10)
    var ans int64

    for i := n - 1; i >= 0; i-- {
        idx := int64(sort.Search(len(alls), func(x int) bool { return alls[x] >= a[i][1] })) + 1
        ans += query(num, idx)
        add(num, idx, int64(n))
    }

    fmt.Println(ans)
}

func main() {
    var T int
    fmt.Fscan(in, &T)

    for tt := 0; tt < T; tt++ {
        solve()
    }

}

 

标签：偏序,return,python,fmt,Codeforces,int,range,int64,func
From： https://www.cnblogs.com/zk6696/p/17936913

相关文章

  • 【Python爬虫课程设计】招聘网站数据分析与可视化
    一、选题背景随着互联网的快速发展和信息化时代的到来，招聘网站成为求职者和招聘公司之间最重要的信息交流平台之一。招聘网站上聚集了大量的职位信息、薪资数据和公司信息，这些数据蕴含着丰富的招聘市场和就业趋势的信息，对求职者和招聘公司都具有重要的参考价值。然而，由于招聘网站......
  • appium-python自动开启和关闭服务（win/mac）
    后台启动&关闭appiumserver的命令启动appium：appium-a127.0.0.1-p4723--logxxx.log--local-timezoneAppium服务命令行参数启动appium-p4723指定端口--logxxx.log指定日志保存到指定文件内（可以是绝对路径）--local-timezone指定时间为本地时间--log-levelerror......
  • Python+自动化测试生成HTML报告
    ......
  • [Codeforces] CF1545A AquaMoon and Strange Sort
    CF1545AAquaMoonandStrangeSort题目传送门题意有\(n\)个人从左到右站成一排，从左数第\(i\)个人的衣服上印着\(a_i\)。每个人的朝向可以是朝左、朝右。一开始所有人的方向都是朝右。您可以对这些人做一些“操作”，每次操作允许您找两个相邻的人让他们交换顺序，但是在操作......
  • [Codeforces] CF1547E Air Conditioners
    CF1547EAirConditioners题目传送门这道题我的思路严重劣于题解思路，所以请慎用但是自认为我的贪心比dp好理解点题意有\(q\)组数据，每组第一排表示有\(n\)个方格和\(k\)个空调，第二排是每个空调的位置\(a_i\),第三排是每个空调的温度\(t_i\)。每个空调对周围的影响......
  • Python教程(18)——python文件操作详解
    所谓的文件操作是指对计算机中的文件进行读取、写入、修改和删除等操作。简单来说可以分为以下三个部分：打开文件操作文件关闭文件就是这三个简简单单的操作，却在计算机世界占有一席之地。打开文件有各种打开模式，各不相同；操作文件，有读写模式；关闭文件就比较简单了。Python文......
  • codeforces刷题（1100）：1862C_div3
    C、FlowerCityFence跳转原题点击此：该题地址1、题目大意  给你n块长度依次不递增的紧密连接在一起的垂直木板，将它们水平横过来，问其组成的全新n块木板的长度是否与原来的木板长度一致。  注意：这里的长度是指：木板的高度。水平摆放后的木板是左对齐，所以其长度就是各个木板水......
  • 大数据分析与可视化 之 实验01 Python爬虫
    实验01Python爬虫实验学时：2学时实验类型：验证实验要求：必修一、实验目的理解爬虫技术掌握正则表达式、网络编程掌握re、socket、urllib、requests、lxml模块及其函数的使用二、实验要求 分析所需爬取信息网页的源代码，使用re、socket、urllib、requests、lxml模块及其函......
  • Python SciPy 空间数据
    SciPy空间数据https://blog.csdn.net/weixin_64338372/article/details/128675235?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522170381772916800222899723%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=170381772916800222899......
  • JS加密，python解密
    `//jsAES加密varCryptoJs=require("crypto-js")//密钥（128位，16字节）varkey=CryptoJs.enc.Utf8.parse("1234567890abcdef");//直接打印为words数组，可用如下方法进行还原//console.log(CryptoJs.enc.Utf8.stringify(key))//初始化向量（128位，16字节）variv=Crypto......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99