CodeForces1165

た入场券 2023-06-02 11:59 25阅读 0赞

# CodeForces1165A #

[CodeForces1165A][]  
水题,数一数后\\(x\\)位里的\\(1\\),注意\\(y+1\\)位是不是\\(1\\)就行了.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 2e5 + 100 ; int n , x , y , ans ; bool v[N] ; char s[N] ; signed main (int argc , char * argv[]) { n = rint () ; x = rint () ; y = rint () ; scanf ("%s" , s + 1 ) ; rep ( i , 1 , n ) v[i] = s[i] == '1' ; per ( i , n , n - x + 1 ) if ( v[i] ) ++ ans ; if ( ! v[n-y] ) ++ ans ; else -- ans ; printf ("%lld\n" , ans ) ; system ("pause") ; return 0 ; }

# CodeForces1165B #

水题,把比赛排个序,能打就打.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 2e6 + 100 ; int n , v[N] , ans ; signed main (int argc , char * argv[]) { n = rint () ; rep ( i , 1 , n ) v[i] = rint () ; sort ( v + 1 , v + n + 1 ) ; int now = 1 , cur = 1 ; while ( true ) { if ( v[cur] >= now ) ++ ans ; else { while ( v[cur] < now && cur <= n ) ++ cur ; if ( cur > n ) break ; ++ ans ; } ++ now ; ++ cur ; } printf ("%lld\n" , ans ) ; system ("pause") ; return 0 ; }

# CodeForces1165C #

水题,从前向后扫原串,能取就取,最后注意取出来的长度就行了.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 2e6 + 100 ; int n , ans ; char s[N] , t[N] ; signed main (int argc , char * argv[]) { n = rint () ; scanf ("%s" , s + 1 ) ; if ( ! ( n & 1 ) ) { bool f = true ; for (int i = 1 ; i <= n - 1 ; i += 2) if ( s[i] == s[i+1] ) { f = false ; break ; } if ( f ) { puts ("0") ; rep ( i , 1 , n ) putchar ( s[i] ) ; putchar ( 10 ) ; system ("pause") ; return 0 ; } } int cur = 0 ; rep ( i , 1 , n ) { if ( cur & 1 ) { while ( s[i] == t[cur] && i <= n ) ++ i ; if ( i > n ) { -- cur ; break ; } t[++cur] = s[i] ; } else t[++cur] = s[i] ; } if ( cur & 1 ) -- cur ; printf ("%lld\n" , n - cur ) ; if ( cur ) rep ( i , 1 , cur ) putchar ( t[i] ) ; putchar(10) ; system ("pause") ; return 0 ; }

# CodeForces1165D #

水题,把给定的因子排个序,取\\(d\_1\\times d\_n\\)为假定答案,然后从两侧向中间扫,遇到矛盾直接\\(-1\\).  
如果通过了上面的检测,就再\\(\\Theta(\\sqrt\{n\})\\)枚举因子,判断是否全部出现即可.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 521 ; const int M = 1e7 + 100 ; int n , d[N] , ans ; bool mk[M] ; signed main (int argc , char * argv[]) { int T = rint () ; while ( T -- ) { n = rint () ; MEM ( mk , 0 ) ; rep ( i , 1 , n ) d[i] = rint () , mk[d[i]] = true ; sort ( d + 1 , d + n + 1 ) ; bool f = true ; int cmp = d[1] * d[n] ; int maxf = n >> 1 ; for (int i = 2 ; i <= maxf ; ++ i) if ( d[i] * d[n-i+1] != cmp ) { f = false ; break ; } if ( n & 1 ) if ( d[maxf+1] * d[maxf+1] != cmp ) f = false ; if ( f ) for (int i = 2 ; i * i <= cmp + 1 ; ++ i) if ( cmp % i == 0 && ( ! mk[i] || ! mk[cmp/i] ) ) f = false ; if ( ! f ) puts ("-1") ; else printf ("%lld\n" , cmp ) ; } system ("pause") ; return 0 ; }

# CodeForces1165E #

有点东西的题目.  
考虑每个位置的贡献,你发现每个位置都是独立的,然后分别考虑贡献就行了.  
贡献就是经过它的区间个数乘上\\(a\\)数组,然后把得到的贡献数组和\\(b\\)反向排序,对应位置统计即可.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 2e5 + 100 ; const int mod = 998244353 ; int n , a[N] , b[N] , ans , pos[N] ; inline bool cmp (int x , int y) { return x > y ; } signed main (int argc , char * argv[]) { n = rint () ; rep ( i , 1 , n ) a[i] = rint () ; rep ( i , 1 , n ) b[i] = rint () ; rep ( i , 1 , n ) pos[i] = a[i] * ( ( i - 1 ) * ( n - i ) + n ) ; sort ( pos + 1 , pos + n + 1 , cmp ) ; sort ( b + 1 , b + n + 1 ) ; rep ( i , 1 , n ) ans = ( ans + pos[i] % mod * b[i] % mod ) % mod ; printf ("%lld\n" , ans ) ; system ("pause") ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11506554.html

[CodeForces1165A]: http://codeforces.com/contest/1165/problem/A