2018-07-23
找规律结论题,只有能整除3或4的才能拆.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 2e5 + 5;
int main()
{
int T; scanf("%d", &T);
while (T--)
{
int n; scanf("%d", &n);
if (n % 3 == 0) printf("%lld\n", 1ll * n * n * n / 27);
else if (n % 4 == 0) printf("%lld\n", 1ll * n * n * n / 32);
else printf("-1\n");
}
return 0;
}
贪心神题,我们都知道是先预处理自己能匹配的,然后安照莫一种顺序排序,但是试了一万种也不行… 这题没意思,没什么好讲的
/* ***********************************************
Author :JiangYu
Created Time :2018年07月23日 星期一 13时41分02秒
File Name :2.cpp
************************************************ */
using namespace std;
#include <bits/stdc++.h>
const int N = 1e5 + 1024;
char str[N];
struct node{
int a, b;
}no[N];
bool cmp(const node &o, const node &p) {
if(o.a >= o.b && p.a < p.b)
return 0;
if(o.a < o.b && p.a >= p.b)
return 1;
if(o.a >= o.b && p.a >= p.b)
return o.b > p.b;
return o.a < p.a;
}
int main()
{
//std::ios::sync_with_stdio(false);
//freopen("out.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
int ans = 0;
for(int i = 1; i <= n; ++i) {
no[i].a = no[i].b = 0;
scanf("%s", str);
int len = strlen(str);
for(int j = 0; j < len; j++)
{
if(str[j] == '(')
no[i].b++;
else
{
//cout << str[j] << endl;
if(no[i].b > 0)
no[i].b--, ans += 2;
else
no[i].a++;
}
}
}
//cout << ans << endl;
sort(no+1, no+1+n, cmp);
int cnt = 0;
for(int i = 1; i <= n; ++i) {
//cout << no[i].b<< " " << no[i].a<<endl;
//cout << cnt << endl;
if(no[i].a > cnt) no[i].a = cnt;
ans += no[i].a*2;
cnt -= no[i].a;
cnt += no[i].b;
}
printf("%d\n", ans);
}
return 0;
}
因为保证了不存在三点共线,按x,y排序就好了.签到题.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 1e3 + 5;
struct Node{
int x, y, id;
bool operator<(const Node& o) const
{
if (x == o.x) return y < o.y;
return x < o.x;
}
}e[3 * N];
int main()
{
int t; scanf("%d", &t);
while (t--)
{
int n; scanf("%d", &n);
n *= 3;
for (int i = 0; i < n; i++)
{
scanf("%d%d", &e[i].x, &e[i].y);
e[i].id = i + 1;
}
sort(e, e + n);
for (int i = 0; i < n; i += 3)
printf("%d %d %d\n", e[i].id, e[i + 1].id, e[i + 2].id);
}
return 0;
}
先把区间排序,然后从左往右,能盖小的就盖小的,用一个set来存能放的值.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 2e5 + 5;
struct Node{
int l, r;
bool operator<(const Node& o) const
{
if (l == o.l) return r > o.r;
return l < o.l;
}
}e[N];
int a[N];
int main()
{
int T; scanf("%d", &T);
while (T--)
{
int n, m; scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
scanf("%d%d", &e[i].l, &e[i].r);
sort(e, e + m);
set<int> S;
for (int i = 1; i <= n; i++) S.insert(i);
int L = 1, R = 0;
for (int i = 0; i < m; i++)
{
while (R < e[i].l - 1) a[++R] = 1;
while (L < e[i].l) S.insert(a[L++]);
while (R < e[i].r)
{
a[++R] = *S.begin();
S.erase(S.begin());
}
}
while (R < n) a[++R] = 1;
for (int i = 1; i <= n; i++)
printf("%d%c", a[i], " \n"[i == n]);
}
return 0;
}
又是一个找规律题,队友写的,这题我基本上没干啥.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 1e3 + 5;
ll f[70], g[70];
int main()
{
g[0] = f[0] = 1;
for (int i = 1; i < 63; i++)
{
f[i] = 2 * f[i - 1] + 1;
g[i] = (2 * g[i - 1] % MOD + (1ll << i) % MOD + (1ll << i - 1) % MOD * (f[i - 1] % MOD) % MOD) % MOD;
// cout << i << " " << g[i] << endl;
}
int t; scanf("%d", &t);
while (t--)
{
ll n; scanf("%lld", &n);
ll ans = 1;
--n;
for (int i = 62; i >= 0; i--)
{
while (n >= f[i])
{
ans = (ans + g[i]) % MOD;
ans = ((1ll << i) % MOD * ((n -= f[i]) % MOD) % MOD + ans) % MOD;
}
}
printf("%lld\n", ans);
}
return 0;
}
这个题很棒啊.首先你要知道什么是笛卡尔树 然后你就会发现$A,B RMQ Similar$就是$A, B$ 笛卡尔树相同. 其次,B的元素是在$0~1$的实数之间均匀分布,则其权值的期望为$ \frac{2}{n}$ 然后笛卡尔树的总数则为$ \frac{n!}{\prod_{i} size_{i}}$ ($n!$ 实际含义为 $ A_{n}^{n} $, $ \frac{n!}{\prod_{i} size_{i}}$ 含义为依次出去每个最大点的儿子数,画图便于理解)
/* ***********************************************
Author :JiangYu
Created Time :2018年07月24日 星期二 10时26分21秒
File Name :8.cpp
************************************************ */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 1024;
int mod = 1e9 + 7;
int a[N];
int stk[N], top, l[N], r[N], p[N];
ll inv[N], ret;
int dfs(int u) {
int s = 1;
if(l[u]) s += dfs(l[u]);
if(r[u]) s += dfs(r[u]);
ret = ret * inv[s] % mod;
return s;
}
void build(int n) {
int top = 0;
for(int i = 1; i <= n; ++i) {
l[i] = 0, r[i] = 0, p[i] = 0;
}
for(int i = 1; i <= n; ++i) {
int k = top;
while(k > 0 && a[stk[k-1]] < a[i]) --k;
if(k) r[stk[k-1]] = i;
if(k < top) l[i] = stk[k];
stk[k++] = i;
top = k;
}
for(int i = 1; i <= n; ++i) {
p[l[i]] = p[r[i]] = 1;
}
int rt = 0;
for(int i = 1; i <= n; ++i) {
if(p[i] == 0) rt = i;
}
dfs(rt);
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
inv[1] = 1;
int n;
for(int i = 2; i <= 1000000; ++i)
inv[i] = inv[mod %i] * (mod - mod/i) % mod;
int t;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
ret = inv[2] * n % mod;
build(n);
printf("%d\n", ret);
}
return 0;
}
论文题,没意思,不补
时区转换,遇到的唯一坑点就是$+0.2$有精度误差,耽误了蛮久.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 2e5 + 5;
int main()
{
int T; scanf("%d", &T);
while (T--)
{
int h, m; double f;
scanf("%d%d UTC%lf", &h, &m, &f);
int t = h * 60 + m - 480;
t += round(f * 60);
t %= 24 * 60;
while (t < 0) t += 24 * 60;
printf("%02d:%02d\n", t / 60, t % 60);
}
return 0;
}