因为不论怎么操作,前面的几次最多带入m-1
,最后一次最多可以带入m
所以我们就能得到一个式子\(k(m-1)+m\ge n\),化简这个式子就能得到\(k\ge \frac{n-m}{m-1}\)
所以答案就是\(2k+1\)次,然后只需解这个不等式即可
#include<bits/stdc++.h> using namespace std; int n , m , res ; void slove() { cin >> n >> m; if( m == 1 ) { if( n <= 1 ) cout << "1\n"; else cout << "-1\n"; return ; } res = ( n - m ) / ( m - 1 ) * 2 ; if( (n-m)%(m-1) ) res += 3; else res += 1; cout << res << endl; return ; } int main() { int t; cin >> t; while( t -- ) slove(); return 0; }
很搞笑,这道题我把这道题做复杂了
先说下真正的正解吧
说完了正解,在说一下我的方法,我的做法可以将\(a_i\)的范围加强到\(1e9\)甚至更大都可以
首先假设我对于我每次枚举的i
之后,我把剩下的数字进行排序,然后我就可以用前缀和,二分把剩下序列分成\(a_i+a_j-1000<0\)和\(a_i+a_j\ge1000\)的部分,设mid
为分界点那么
第二行就是前半部分,第三方就是后半部分,这里的\(a_k\)是已经排序后的
所以求解该式子需要先二分求出\(mid\),然后前缀和即可,复杂度为\(O(\log n)\)
但是前提是每次都需要排序,在前缀和,所以求解真正复杂度应该是\(O(n\log n)\),那么整体的复杂度就是\(O(n^2\log n)\),这是基础的做法,然后讲优化
首先把a
数组赋值给b
并且排序,再用树状数组c
维护b
的前缀和,然后再用一个树状数组d
维护一个全是1
的数组的前缀和,d
数组代表的就是b
数组的每一位数字是否存在
每次对于一个a[i]
在b
数组中二分出\(a_j\ge 1000-a_i\)的最小值就是mid
,然后用c,d
两个数组就可以求解上面的式子,然后二分出a[i]
在b
中的位置,并且在c,d
中的该位置分别加上-a[i],-1
,这样在后面的过程中a[i]
就被删除了
所以用两个树状数组的方法来优化复杂度就是\(O(n\log n)\)
#include <bits/stdc++.h> #define ll long long #define lowbit( x ) ( x & -x ) using namespace std; const int N = 1e6 + 5; int n , a[N] , b[N] ; ll c[N] , d[N] , res; inline int read() { int x = 0 , ch = getchar(); while( ch < '0' || ch > '9' ) ch = getchar(); while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar(); return x; } void update( int x , int v , ll bit[] ) { for( int i = x ; i <= n ; i += lowbit(i) ) bit[i] += v; } ll get( int x , ll bit[] ) { ll ans = 0; for( int i = x ; i ; i -= lowbit(i) ) ans += bit[i]; return ans; } int main() { n = read(); for( int i = 1 ; i <= n ; i ++ ) a[i] = b[i] = read(); sort( b + 1 , b + 1 + n ); for( int i = 1 ; i <= n ; i ++ ) update( i , b[i] , c ) , update( i , 1 , d ); for( ll i = 1 , t , mid , k , sum , cnt; i <= n ; i ++ ) { t = 1000 - a[i]; mid = lower_bound( b + 1 , b + 1 + n , t ) - b; cnt = get( mid - 1 , d ) , sum = get( mid - 1 , c ); res += ( cnt * 2 + i - n - 1 ) * t + get( n , c ) - 2 * sum ; k = lower_bound( b + 1 , b + 1 + n , a[i] ) - b; update( k , -1 , d ) , update( k , -a[i] , c ); } cout << res << endl; }
要保证a的数量一定是大于等于b的情况下,排个序贪心的选择就好了
#include<bits/stdc++.h> using namespace std; const int N = 1e4+5; long long n , sa , a , b , va[N] , vb[N] , res; inline int read() { int x = 0 , ch = getchar(); while( ch < '0' || ch > '9' ) ch = getchar(); while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar(); return x; } void slove() { sa = a = read() , b = read() , n = read(); for( int i = 1 ; i <= a ; i ++ ) va[i] = read(); sort( va + 1 , va + 1 + a , greater<int>() ); for( int i = 1 ; i <= b ; i ++ ) vb[i] = read(); sort( vb + 1 , vb + 1 + b , greater<int>() ); b = min( b , n / 2 ) , a = min( a , n - b ); if( a + b < n ) { cout << "-1\n"; return ; } res = 0 ; while( a < sa && va[ a+1 ] > vb[b] ) a ++ , b --; for( int i = 1 ; i <= a ; i ++ ) res += va[i]; for( int i = 1 ; i <= b ; i ++ ) res += vb[i]; cout << res << endl; } int main() { int t = read(); while( t -- ) slove(); return 0; }
按照题目进行模拟不断地维护最大值即可
#include<bits/stdc++.h> using namespace std; int n ; string op; void slove() { cin >> n >> op; double x = 0 , y = 0 , res = 0; for( auto it : op ) { if( it == 'L' ) x --; else if( it == 'R' ) x ++; else if( it == 'U' ) y ++; else y --; res = max( res , sqrt( x * x + y * y ) ); } printf( "%.7lf\n" , res ); return ; } int main() { int t; cin >> t; while( t -- ) slove(); return 0; }
这道题就是从后向前找一个不上升子序列,而且不能不选,开头也确定了
这道题的位置算是给无用的信息
#include <bits/stdc++.h> using namespace std; const int N = 1e5+5; int n , a[N] , t , cnt; int main() { cin >> n; for( int i = 1 , x ; i <= n ; i ++ ) cin >> x >> a[i]; t = a[n]; for( int i = n ; i >= 1 ; i -- ) { if( a[i] > t ) continue; t = a[i] , cnt ++; } cout << cnt << endl; return 0; }
这道题的解法还是很多
最好理解的就是双指针,先按照位置排个序,然后同时维护l,r
两个指针,保证指针的间距小于2k
就行
#include <bits/stdc++.h> #define w first #define v second using namespace std; const int N = 1e5+5; int n , k , sum , res , l , r; pair< int , int > g[N]; int main() { cin >> n >> k; for( int i = 1 ; i <= n ; i ++ ) cin >> g[i].v >> g[i].w; sort( g + 1 , g + 1 + n ) , k *= 2; for( int l = 1 , r = 1 ; r <= n ; r ++ ) { sum += g[r].v; while( g[r].w - g[l].w > k ) sum -= g[ l ++ ].v; res = max( res , sum ); } cout << res << endl; return 0; }
然后我发现这里\(x_i\)的范围很小自由1e6
,就完全可以用前缀和做,枚举每个区间就好了
#include <bits/stdc++.h> #define w first #define v second using namespace std; const int N = 1e6+5; int n , k , res , v[N] , m ; int main() { cin >> n >> k; for( int i = 1 , x , y; i <= n ; i ++ ) scanf("%d%d" , &x , &y ) , m = max( m , y ), v[y] += x; for( int i = 1 ; i <= m ; i ++ ) v[i] += v[ i - 1 ]; k = k * 2 + 1 ; if( k >= m ) { cout << v[m] << endl; return 0; } for( int l = 0 , r = k ; r <= m ; r ++ , l ++ ) res = max( res , v[r] - v[l] ); cout << res << endl; return 0; }
如果说前缀和是站在牛的角度,还有就是可以差分站在草的角度做
如果草的位置是x
那么在,草在x-k
到x+k
的贡献都是g
,很简单前缀和维护就好了
#include <bits/stdc++.h> #define w first #define v second using namespace std; const int N = 3e6+10; int n , k , res , v[N] , m ; int main() { cin >> n >> k; for( int i = 1 , l , r , x , y ; i <= n ; i ++ ) { cin >> x >> y; l = max( 1 , y - k ) , r = y + k , m = max( m , r ); v[l] += x , v[r+1] -= x; } for( int i = 1 ; i <= m ; i ++ ) v[i] += v[i-1] , res = max( res , v[i] ); cout << res << endl; return 0; }
前缀和的话要注意一下数组的范围应该是a+k
也就是3e6
不过也能过
这道题就是很简单的思维题了
#include <bits/stdc++.h> using namespace std; string s; long long a , b , c; int main() { cin >> s >> s; for( auto it : s ) { if( it == 'C' ) a ++; else if( it == 'O' ) b += a; else c += b; } cout << c << endl; return 0; }
非常简单的模拟
#include <bits/stdc++.h> using namespace std; string s; set<char> t; int main() { t.insert('a'),t.insert('e'),t.insert('i'),t.insert('o'),t.insert('u'),t.insert('y'); cin >> s; for( auto & it : s ) if( it >= 'A' && it <= 'Z' ) it = it - 'A' + 'a'; for( int i = 0 ; i < s.size() ; i ++ ) { if( t.find(s[i]) != t.end() ) continue; cout <<'.'<< s[i]; } return 0; }
其实就是统计一下字母的数量,用python很简单的
t = ["a","e","i","o","u"] a = input() b = input() c = input() x = 0 y = 0 z = 0 for i in t: x += a.count(i) y += b.count(i) z += c.count(i) if( x == 5 and y == 7 and z == 5 ): print("YES") else : print("NO")
这道比第一道更加的签到
#include <bits/stdc++.h> #define ll long long using namespace std; int n1 , n2 , n3 , n4; int main() { cin >> n1 >> n2 >> n3 >> n4; cout << ( ((n1^n2) & (n3 | n4)) ^ ((n2&n3) | (n1^n4)) ) << endl; return 0; }
就是一个循环就好
#include <bits/stdc++.h> #define ll long long using namespace std; int n; string s[2] = {"that I love ","that I hate "}; int main() { cin >> n; cout << "I hate "; swap( s[1] , s[0] ); for( int i = 1 ; i < n ; i ++ ) cout << s[i%2]; cout << "it"; return 0; }
把输入的数字排个序,从大到小依次先开方再平方不想等的就是答案
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1005; int n , a[N] , ans; int main() { cin >> n; for( int i = 1 ; i <= n ; i ++ ) cin >> a[i]; sort( a + 1 , a + 1 + n , greater<int>()); for( int i = 1 , t ; i <= n ; i ++ ) { t = sqrt( a[i] ); if( t * t != a[i] ) { cout << a[i] << endl; return 0; } } return 0; }
两重循环喽
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 30005; int n; string s[N]; int main() { cin >> n; for( int i = 1 ; i <= n ; i ++ ) cin >> s[i]; for( int i = 0 ; i < s[1].size() ; i ++ ) for( int j = 2 ; j <= n ; j ++ ) if( s[1][i] != s[j][i] ) { cout << i << endl; return 0; } cout << s[1].size() << endl; return 0; }
数字太少,直接打表
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 30005; int a , b; string s[] = {"" , "1/1" , "5/6" , "2/3" , "1/2" , "1/3" , "1/6" }; int main() { cin >> a >> b; a = max( a , b ); cout << s[a] << endl; return 0; }
情况只有三中间,边,顶点,所以特判一下就好
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 30005; int a , b; int y; char x; int main() { cin >> x >> y; if( x >= 'b' && x <= 'g' && y >= 2 && y <= 7 ) cout << "8\n"; else if( ( x == 'a' || x == 'h' ) && ( y == 1 || y == 8 ) ) cout << "3\n"; else cout << "5\n"; return 0; }
跳过0就好了,特判第一个不输出加号
#include <bits/stdc++.h> #define ll long long using namespace std; ll res , m , n; string s; int main() { cin >> m >> s; n = s.size(); for( int i = 0 ; i < s.size() ; i ++ ) { n --; if( s[i] == '0' ) continue; if( i != 0 ) cout << "+"; cout << s[i] << "*" << m <<"^"<< n; } return 0; }
90分很好做,就是dfs加点剪枝记忆化
#include<bits/stdc++.h> using namespace std; const int N = 20; double n,ans = 0x7f7f7f7f; double x[N] = {},y[N] = {},f[N][N] = {}; bool vis[N] = {}; inline void dfs(int id,double now,int dep) { if(now > ans) return ; if(dep == n) { ans = min(ans,now); return ; } for(int i = 1 ;i <= n;i++) { if(!vis[i]) { if(f[id][i]) { vis[i] = 1; dfs(i,now+f[i][id],dep+1); vis[i] = 0; } else { f[id][i] = sqrt((x[id]-x[i])*(x[id]-x[i]) + (y[id]-y[i])*(y[id]-y[i]) ); f[i][id] = f[id][i]; vis[i] = 1; dfs(i,now+f[id][i],dep+1); vis[i] = 0; } } } } int main() { cin >> n; if(!n) { puts("0.00"); return 0; } for(register int i = 1;i <= n;i++) cin >> x[i] >> y[i]; dfs(0,0,0); printf("%.2lf",ans); return 0; }
如果剩余的加当前的大于等待长度就把剩余的先处理完,在放入
只要能完整的处理一秒就一直做
这道题我比赛是只拿到70分,因为没有开long long
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5+5; ll n , m , k , last , res; ll a[N]; inline int read() { int x = 0 , ch = getchar(); while( ch < '0' || ch > '9' ) ch = getchar(); while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar(); return x; } int main() { n = read() , m = read() , k = read(); for( int i = 1 ; i <= n ; i ++ ) a[i] = read(); for( int i = 1 ; i <= n ; i ++ ) { if( last + a[i] > m ) res ++ , last = 0; last += a[i]; res += last / k , last %= k; } if( last ) res ++; cout << res << endl; }
这道题其实很暴力,就是先按照题目要求对边排序,然后依次判断边是否是key road
即可
怎么判断呢?就是把除了这条边以外所有的边加入并查集,然后判断是否有一组点是不连通的就行
#include <bits/stdc++.h> #define ll long long #define u first #define v second using namespace std; const int N = 155 , M = 5005l; int n , m , fa[N]; pair< int , int > e[M]; inline int read() { int x = 0 , ch = getchar(); while( ch < '0' || ch > '9' ) ch = getchar(); while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar(); return x; } inline int getfa( int x ) { if( fa[x] == x ) return x; return fa[x] = getfa( fa[x] ); } inline void merge( int x , int y ) { x = getfa( x ) , y = getfa(y) ,fa[y] = x; } int main() { n = read() , m = read(); for( int i = 1 ; i <= m ; i ++ ) { e[i].u = read() , e[i].v = read(); if(e[i].u>e[i].v) swap( e[i].u , e[i].v); } sort( e + 1 , e + 1 + m ); for( int t = 1 ; t <= m ; t ++ ) { for( int i = 1 ; i <= n ; i ++ ) fa[i] = i; for( int i = 1 ; i <= m ; i ++ ) { if( i == t ) continue; merge( e[i].u , e[i].v ); } for( int i = 1 , fi , flag = 1 ; flag && i <= n ; i ++ ) { fi = getfa(i); for( int j = i + 1 ; flag && j <= n ; j ++ ) { if( fi == getfa(j) ) continue; cout << e[t].u << " " << e[t].v << endl; flag = 0; } } } return 0; }
其实可以把这个题理解成给一张图,要求每条边的两个点位于不同的集合中
这里我们可以用划分集合来表示,如果一条边的相同的集合中这一定不行
如果a
于b
相连,那么b
一定于a
相连的点在一个集合中
我代码中的color[x]
,表示与x
相连的点的集合
对于集合的为何这里需要用带权并查集
#include <bits/stdc++.h> using namespace std; const int N = 10005; int n,m,result,father[N],color[N],size[N]; bool f[N]; inline int read() { register int x = 0; register char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') { x = (x<<3)+(x<<1) + ch - '0'; ch = getchar(); } return x; } inline int getfather(int x) { if(father[x] == x) return x; return father[x] = getfather(father[x]); } inline void merge(int x,int y) { if(x == y) return ; father[y] = x; size[x] += size[y]; } int main() { n = read(); m = read(); for(register int i = 1; i <= n; i ++) { father[i] = i; size[i] = 1; } for(register int i = 1;i <= m;i ++) { register int u = read(), v = read(), fu = getfather(u), fv = getfather(v); if(fu == fv) { puts("Impossible"); return 0; } if(color[u]) merge(getfather(color[u]),fv); if(color[v]) merge(getfather(color[v]),fu); color[u] = fv; color[v] = fu; } for(register int i = 1;i <= n;i ++) { register int q = getfather(i); if(f[q]) continue; register int p = getfather(color[i]); f[q] = f[p] = 1; result += min(size[q],size[p]); } printf("%d\n",result); return 0; }
50分做法就暴力的排序喽
#include <bits/stdc++.h> #define ll long long using namespace std; ll n , m; vector<ll> v; inline ll read() { ll x = 0 , ch = getchar(); while( ch < '0' || ch > '9' ) ch = getchar(); while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar(); return x; } int main() { n = read() , m = read(); for( ll x ; n ; n -- ) x = read() , v.push_back(x); sort( v.begin() , v.end() , greater<ll>() ); for( ll op , x ; m ; m -- ) { op = read() , x = read(); if( op == 1 ) printf("%lld\n" ,v[x-1] ); else v.push_back(x) , sort( v.begin() , v.end() , greater<ll>() ); } return 0; }
100分做法就是插入在小于等于它的位置就行
#include <bits/stdc++.h> #define ll long long using namespace std; ll n , m; vector<ll> v; inline ll read() { ll x = 0 , ch = getchar(); while( ch < '0' || ch > '9' ) ch = getchar(); while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar(); return x; } int main() { n = read() , m = read(); for( ll x ; n ; n -- ) x = read() , v.push_back(x); sort( v.begin() , v.end() , greater<ll>() ); for( ll op , x ; m ; m -- ) { op = read() , x = read(); if( op == 1 ) printf("%lld\n" ,v[x-1] ); else v.insert( lower_bound( v.begin() , v.end() , x , greater<ll>() ) , x ); } return 0; }