ARC 068
C - X: Yet Another Die Game
显然最多的就是一次6一次5
最后剩下的可能需要多用一次6或者6和5都用上
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 3005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int64 s,n;
void Solve() {
read(s);
n = (s / 11) * 2;
s %= 11;
if(s > 0 && s <= 6) n += 1;
if(s > 6) n += 2;
out(n);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
D - Card Eater
就是奇数的卡片最后肯定能全消掉，只剩一个
偶数的卡片最后会剩两个，看看两两配对，最后会不会剩一个，剩一个证明肯定需要少一种数，否则就是原来序列中不同的数的个数
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
map<int,int> zz;
int N;
int a[MAXN];
void Solve() {
read(N);
int cnt = 0,p = 0;
for(int i = 1 ; i <= N ; ++i) {
read(a[i]);
zz[a[i]]++;
}
for(auto t : zz) {
++cnt;
if(t.se % 2 == 0) p ^= 1;
}
out(cnt - p);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
E - Snuke Line
对于一个d来说，我们把大于等于d的区间全部删掉
然后给(l - 1)标记成+1，(r)标记成-1，这些区间里能被d访问到的个数是
d - 1的前缀和2d - 1的前缀和，3d - 1的前缀和....
直接树状数组维护就好了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M;
int tr[MAXN],ans[MAXN];
pii p[MAXN];
int lowbit(int x) {return x & (-x);}
void insert(int x,int v) {
++x;
while(x <= M + 1) {
tr[x] += v;
x += lowbit(x);
}
}
int query(int x) {
int v = 0;++x;
while(x > 0) {
v += tr[x];
x -= lowbit(x);
}
return v;
}
void Solve() {
read(N);read(M);
for(int i = 1 ; i <= N ; ++i) {
read(p[i].fi);read(p[i].se);
--p[i].fi;
insert(p[i].fi,1);insert(p[i].se,-1);
}
sort(p + 1,p + N + 1,[](pii a,pii b){return a.se - a.fi < b.se - b.fi;});
int id = N;
int cnt = 0;
for(int i = M ; i >= 1 ; --i) {
while(id >= 1 && p[id].se - p[id].fi >= i) {
insert(p[id].fi,-1);insert(p[id].se,1);
++cnt;--id;
}
ans[i] = cnt;
int t = i;
while(t <= M) {
ans[i] += query(t - 1);
t += i;
}
}
for(int i = 1 ; i <= M ; ++i) {out(ans[i]);enter;}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
F - Solitaire
大意是有一个双端队列，从1到N往里面扔数，再从队首或者队尾取数，要求第K个必须是1，求方案数
这个就看什么样的是合法的，我们发现如果当前没选到1，已经选了i个数，最小的是j，我们要么就选一个比j还小的，要么选一个当前没选过的最大的
这个可以用前缀和优化去dp
当选到第k个之后，就是剩下的序列要么选最大的，要么选最小的，看看乘上2的多少次方就行了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int MOD = 1000000007;
int K,N;
int dp[2005][2005],sum[2005];
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
void Solve() {
read(N);read(K);
dp[0][N + 1] = 1;
for(int i = 1 ; i <= K ; ++i) {
sum[N + 2] = 0;
for(int j = N + 1 ; j >= 1 ; --j) sum[j] = inc(sum[j + 1],dp[i - 1][j]);
for(int j = 1 ; j <= N ; ++j) {
if(i == K && j != 1) continue;
if(i < K && j == 1) continue;
dp[i][j] = sum[j + 1];
if((N - j + 1) > (i - 1)) dp[i][j] = inc(dp[i][j],dp[i - 1][j]);
}
}
int t = 1;
for(int i = 1 ; i < N - K ; ++i) {
t = mul(t,2);
}
out(mul(dp[K][1],t));enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}