A - Easy (h)-index
签到。
Code
/*
* Author: heyuhhh
* Created Time: 2019/10/29 11:58:23
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
const int MAXN = 2e5+5;
typedef long long ll;
int n,a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin>>n){
for(int i=0;i<=n;i++)cin>>a[i];
int ans = 0;
ll sum1=0,sum2=0;
for(int i=n;i>=1;i--){
sum1+=a[i];
if(sum1 >= i)ans=max(ans,i);
}
cout<<ans<<'
';
}
return 0;
}
B - Higher (h)-index
题意：
定义(h)指数为现在至少有(h)篇论文，它的被引用次数至少为(h)。
现在你要开始写论文，若在一篇论文上花(x)小时，则会被引用(acdot x)次；同时，写一篇论文的时候，也可以引用之前自己写过的论文。
现在共有(n)小时来分配写论文，问最大的(h)指数为多少。
思路：
被这个题卡了两个小时...二分思路其实很早就有了，但是细节没有考虑清楚。
- 显然(h)指数具有单调性，故二分(h)，那么我们接下来就是判断(n)个小时能否通过合理的分配，最终满足(h)指数。
- 首先肯定要写(h)篇论文，并且每篇尽可能应用前面的文章，那么最后得到的引用序列就为：(a+h-1,a+h-2,cdots,a)。
- 注意到这个值是连续下降的，观察发现我们每次多花一个小时写一篇新论文，则(1)到(h)号论文中至多有一篇的引用次数会增加到(h)，等价于在这篇论文上多花一个小时来达到目标。
- 所以策略就是判断(a)和(h)的大小关系，若(h<a)，那么就在后面新写(a-h)篇论文即可。
代码很短：
Code
/*
* Author: heyuhhh
* Created Time: 2019/11/3 11:29:12
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
int n,a;
bool chk(int h) {
ll t = h;
if(h > a) {
t += h - a;
}
return t <= n;
}
void run() {
int l = 0, r = n + 1, mid;
while(l < r) {
int mid = (l + r) >> 1;
if(chk(mid)) l = mid + 1;
else r = mid;
}
cout << l - 1 << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin>>n>>a) run();
return 0;
}
C - Just (h)-index
似乎是个主席树裸题...
Code
#include<bits/stdc++.h>
#define mid l+((r-l)>>1)
const int MAXN = 1e5+5;
using namespace std;
int n,q,a[MAXN],tot,rt[MAXN],sz[MAXN*20],lc[MAXN*20],rc[MAXN*20];
void build(int *o,int l,int r){
*o = ++tot;
sz[*o] = 0;
if(l==r)return ;
int m=mid;
build(&lc[*o],l,m);build(&rc[*o],m+1,r);
}
void insert(int *o,int u,int v){
int l=1,r=n,m;
while(l!=r){
m=mid;
sz[*o=++tot] = sz[u] + 1;
if(v<=m)rc[*o]=rc[u],o=&lc[*o],u=lc[u],r=m;
else lc[*o]=lc[u],o=&rc[*o],u=rc[u],l=m+1;
}
sz[*o=++tot] = sz[u]+1;
}
int query(int u,int o,int l,int r,int sum){
if(l==r)return l;
int m = mid;
int s = sz[rc[o]] - sz[rc[u]];
if(sum + s >= m+1)return query(rc[u],rc[o],m+1,r,sum);
else{
return query(lc[u],lc[o],l,m,sum + s);
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
while(cin>>n>>q){
for(int i=1;i<=n;i++)cin>>a[i];
tot=0;
build(&rt[0],1,n);
for(int i=1;i<=n;i++){
insert(&rt[i],rt[i-1],a[i]);
}
while(q--){
static int l,r;
cin>>l>>r;
cout<<query(rt[l-1],rt[r],1,n,0)<<'
';
}
}
return 0;
}
F - Sorting
直接按规则排序即可，因为涉及到分数，通分又会爆long long，所以手写一个分数类。但这还不够，最后比较分数的大小的时候辗转相除一下即可。复杂度多个(logn).
Code
/*
* Author: heyuhhh
* Created Time: 2019/10/29 11:58:23
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
const int MAXN = 2e5+5;
typedef long long ll;
typedef unsigned long long ull;
int n;
inline int cmp(ull a,ull b,ull c,ull d){
if(a/b == c/d){
if(a%b==0&&c%d==0)return 0;
else if(a%b==0 && c%d!=0)return -1;
else if(a%b!=0 && c%d==0)return 1;
return -cmp(b,a%b,d,c%d);
}
else{
return a/b < c/d?-1:1;
}
}
struct frac{
ull x,y;
int id;
bool operator <(const frac&rhs)const{
int d = cmp(x,y,rhs.x,rhs.y);
if(d==0)return id<rhs.id;
else{
return d==-1?true:false;
}
}
}a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin>>n){
ull x,y,z;
for(int i=1;i<=n;i++){
cin>>x>>y>>z;
a[i].x = (x+y);
a[i].y = (x+y+z);
a[i].id = i;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)cout<<a[i].id<<"
"[i==n];
}
return 0;
}
G - String Transformation
题意：
给出只由(a,b,c)构成的(S)串和(T)串，现在有三种特殊的串(aa,bb,abab)，可以在(S)串中任意插入或者删除，问最后能否变为(T)串。
思路：
- 因为特殊字符串不涉及(c)，所以相当于(c)为分隔符，现在只用考虑全由(a,b)构成的两个字符串是否相等。
- 注意一个特殊的东西：(ab)可以变为(ba)，(ba)也可以变为(ab)。
- 那么可以大力猜测最终倘若把字符串化为最简，是由很少的几个字符构成。
- 因为无论删除(aa,bb)还是(abab)，(a,b)个数的奇偶性不会发生改变，那么我们直接根据两个串的(a,b)奇偶性来判断就行。
- 正确性：假设我们全都删掉连续的相同的，并且把一些连续的(abab)删掉，显然最后只有可能是(aba,emptyset,a,b,ab)这几种情况，然后就可以发现与奇偶性相关了。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2019/11/3 11:29:12
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e4 + 5;
int n, m;
char s[N], t[N];
void run(){
n = strlen(s + 1), m = strlen(t + 1);
int c1 = 0, c2 = 0;
for(int i = 1; i <= n; i++) c1 += (s[i] == 'c');
for(int i = 1; i <= m; i++) c2 += (t[i] == 'c');
if(c1 != c2) {
cout << "No" << '
';
return;
}
int i = 1, j = 1;
int s_a = 0, s_b = 0, t_a = 0, t_b = 0;
while(i <= n || j <= m) {
while(i <= n && s[i] != 'c') {
if(s[i] == 'a') ++s_a;
else ++s_b;
++i;
}
while(j <= m && t[j] != 'c') {
if(t[j] == 'a') ++t_a;
else ++t_b;
++j;
}
++i, ++j;
if(((s_a & 1) == (t_a & 1)) && ((s_b & 1) == (t_b & 1))) {
s_a = s_b = t_a = t_b = 0;
}
else {
cout << "No" << '
';
return;
}
}
cout << "Yes" << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin >> (s + 1) >> (t + 1)) run();
return 0;
}
J - Vertex Cover
题意：
给出一个完全图，第(i)个点的权值为(2^i)。
询问有多少种选边方式，使得覆盖这些边的点集之和为(k)（给出其二进制表示）。
定义覆盖一条边即为这条边的两个端点至少有一个点被选中。
同时，选择点去覆盖边时，尽量选择权值之和较小的点。也就是说，对于一条边的两个点，只选择权值较小的那一个点即可，不选择另一端点（假设图中只有这一条边）。
思路：
- 按二进制位从高到底考虑：
- 假设当前为(1)，设前面有(a)个(1)，(b)个(0)，那么方案数为((2^b-1)cdot 2^a)，表示至少连向一个(0)，同时可以任意连向(1)，这样可以保证这个(1)必选；
- 如果当前为(0)，方案数为(2^a)，表示可以随便连向前面的(1)，因为前面的(1)必选，所以这个(0)必然不会选。
- 然后就没了。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2019/11/3 11:29:12
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1e9+7,MAXN=1e5+5;
//head
int n,pw[MAXN];
char s[MAXN],t[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
pw[0]=1;
for(int i=1;i<=100000;i++)pw[i] = pw[i-1]*2%MOD;
while(cin>>n){
cin>>t;
int len =strlen(t);
for(int i=0;i<n-len;i++)s[i]='0';
for(int i=0;i<len;i++)s[n-len+i] = t[i];
int cnt=0;
ll ans=1;
for(int i=0;i<n;i++){
if(s[i]=='1')ans = ans*((pw[i-cnt]-1+MOD)%MOD)%MOD*pw[cnt]%MOD;
else ans=ans*pw[cnt]%MOD;
if(s[i]=='1')cnt++;
}
cout<<ans<<'
';
}
return 0;
}
K - 2018
题意：
给出(a,b,c,d)，问有多少对((x,y))，满足(aleq xleq b,cleq yleq d)，且(xcdot y|2018)。
思路：
分情况讨论即可：
- (x)为(1009)的奇数倍；
- (x)为(1009)的偶数倍；
- (x)为偶数且不为(1009)的倍数；
- (x)为奇数且不为(1009)的倍数。
这样就能覆盖所有情况了。
Code
/*
* Author: heyuhhh
* Created Time: 2019/10/29 11:58:23
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
const int MAXN = 2e5+5;
typedef long long ll;
ll a,b,c,d;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin>>a>>b>>c>>d){
ll ans=0;
ans += (b/2018 -(a-1)/2018) * (d-c+1);
ans += ((b/1009 - (a-1)/1009) - (b/2018 - (a-1)/2018)) * (d/2 -(c-1)/2);
ans += (b/2 - (a-1)/2 - (b/2018 - (a-1)/2018)) * (d/1009 - (c-1)/1009);
ans += (b-a+1 - (b/2 - (a-1)/2) - ((b/1009 - (a-1)/1009) - (b/2018 - (a-1)/2018))) * (d/2018 - (c-1)/2018);
cout<<ans<<'
';
}
return 0;
}