比赛传送门：↵
[contest:319429]↵
↵
Idea:[user:aabbccSu,2021-03-13]↵
↵
[tutorial:319429A]↵
↵
------↵
↵
Idea:[user:SHIYAOHUA,2021-03-13]↵
↵
[tutorial:319429B]↵
↵
------↵
↵
Idea:[user:waswasqq,2021-03-13]↵
↵
[tutorial:319429C]↵
↵
------↵
↵
Idea:[user:hushnow,2021-03-13]↵
↵
[tutorial:319429D]↵
↵
------↵
↵
Idea:[user:tczzz,2021-03-13]↵
↵
[tutorial:319429E]↵
↵
------↵
↵
Idea:[user:rainbu5,2021-03-13]↵
↵
[tutorial:319429F]↵
↵
------↵
↵
Idea:[user:SCUEC_Lyh,2021-03-13]↵
↵
[tutorial:319429G]↵
↵
------↵
↵
Idea:[user:lancee,2021-03-13]↵
↵
[tutorial:319429H]↵
↵
------↵
↵
Idea:[user:Visors,2021-03-13]↵
↵
粗暴复刻了↵
[problem:1345C]↵
↵
[tutorial:319429I]↵
↵
------↵
↵
Idea:[user:twh12138,2021-03-13]↵
↵
[tutorial:319429J]↵
↵
------↵
↵
Idea:[user:CofDoria,2021-03-13]↵
↵
[tutorial:319429K]↵
↵
------↵
↵
Idea:[user:lqrs,2021-03-13]↵
↵
[tutorial:319429L]↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <unordered_map>↵
↵
using namespace std;↵
#define ENDL "\n"↵
#define lowbit(x) (x & (-x))↵
typedef long long ll;↵
typedef long double ld;↵
typedef unsigned long long ull;↵
typedef pair<int, int> pii;↵
typedef pair<ll, ll> pll;↵
typedef pair<double, double> pdd;↵
const double eps = 1e-8;↵
const double pi = acos(-1.0);↵
const int inf = 0x3f3f3f3f;↵
const double dinf = 1e300;↵
const ll INF = 1e18;↵
const int Mod = 1e9 + 7;↵
const int maxn = 2e5 + 10;↵
↵
bool isLeap(int x) {↵
if ((x % 4 == 0 && x % 100) || x % 400 == 0) return 1;↵
return 0;↵
}↵
↵
↵
int p[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};↵
int q[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};↵
int v[] = {0, 1, 2, 4, 8, 16, 32};↵
↵
//2021/1/1 Friday↵
int getWeek(int Y, int M, int D) {↵
int y = 2021, m = 1, d = 1, w = 5;↵
while (y != Y || m != M || d != D) {↵
if (!isLeap(y)) {↵
if (d + 1 > p[m]) {↵
if (m + 1 > 12) y++, m = 1, d = 1;↵
else {↵
m++;↵
d = 1;↵
}↵
} else d++;↵
} else {↵
if (d + 1 > q[m]) {↵
if (m + 1 > 12) y++, m = 1, d = 1;↵
else {↵
m++;↵
d = 1;↵
}↵
} else d++;↵
}↵
↵
w = w + 1 > 7 ? 1 : w + 1;↵
}↵
return w;↵
}↵
↵
int solve(int y, int m, int d, int w, int Y, int M, int D) {↵
int ans = 0;↵
while (y != Y || m != M || d != D) {↵
if (!isLeap(y)) {↵
if (d + 1 > p[m]) {↵
if (m + 1 > 12) y++, m = 1, d = 1;↵
else {↵
m++;↵
d = 1;↵
}↵
} else d++;↵
} else {↵
if (d + 1 > q[m]) {↵
if (m + 1 > 12) y++, m = 1, d = 1;↵
else {↵
m++;↵
d = 1;↵
}↵
} else d++;↵
}↵
if (w < 7) ans += v[w];↵
else ans /= 2;↵
w = w + 1 > 7 ? 1 : w + 1;↵
}↵
if (w < 7) ans += v[w];↵
else ans /= 2;↵
return ans;↵
}↵
↵
//首先计算出起始天是周几，然后向后模拟↵
int main() {↵
//freopen("in.txt","r",stdin);↵
//freopen("out.txt","w",stdout);↵
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);↵
int T;↵
int y1, m1, d1, y2, m2, d2;↵
cin >> T;↵
while (T--) {↵
cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;↵
int now = getWeek(y1, m1, d1);↵
cout << solve(y1, m1, d1, now, y2, m2, d2) << ENDL;↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:SHIYAOHUA,2021-03-13]↵
↵
[tutorial:319429B]↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define ENDL "\n"↵
↵
char s[20];↵
↵
int main() {↵
int T, n;↵
scanf("%d", &T);↵
while (T--) {↵
scanf("%d", &n);↵
double sum = 0.0;↵
int cnt = 0;↵
for (int i = 1; i <= n; i++) {↵
scanf("%s", s);↵
if (isalpha(s[0])) continue;↵
else {↵
sum += atof(s), cnt++;↵
}↵
}↵
if (cnt == 0) puts("0");↵
else printf("%.10lf\n", sum / cnt);↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:waswasqq,2021-03-13]↵
↵
[tutorial:319429C]↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
typedef long long ll;↵
const int mod = 1e9 + 7;↵
↵
int main() {↵
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);↵
int t;↵
//scanf("%d",&t);↵
cin >> t;↵
while (t--) {↵
int n;;↵
//scanf("%d",&n);↵
cin >> n;↵
ll sum = 0;↵
for (int i = 0; i < n; i++) {↵
int x;↵
//scanf("%d",&x);↵
cin >> x;↵
sum += x;↵
sum %= mod;↵
}↵
n--;↵
while (n--)//也可以手写快速幂↵
{↵
sum *= 2;↵
sum %= mod;↵
}↵
//printf("%d\n",sum);↵
cout << sum << '\n';↵
}↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:hushnow,2021-03-13]↵
↵
[tutorial:319429D]↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
#define ll long long↵
int n, m;↵
int dx[] = {0, 1, 0, -1};↵
int dy[] = {-1, 0, 1, 0};//方向数组↵
bool tu[5][5];//表示是否走过↵
int sum = 0;↵
↵
void dfs(int x, int y, int num)//x，y是当前到的格子，num是当前已经排了的蛇的长度↵
{↵
if (num == m)//当排到蛇的长度为m时即可认为是一种情况，并sum++↵
{↵
sum++;↵
return;↵
}↵
for (int i = 0; i < 4; i++) {↵
if (x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < n && (!tu[x + dx[i]][y + dy[i]])) {↵
tu[x + dx[i]][y + dy[i]] = true;//走过的用true表示已经走过↵
dfs(x + dx[i], y + dy[i], num + 1);↵
tu[x + dx[i]][y + dy[i]] = false;//递归回来后将其再次标记为未走过↵
}↵
}↵
}↵
↵
int main() {↵
cin >> n >> m;↵
memset(tu, false, sizeof(tu));//将图表示为都没有走过↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < n; j++) {↵
tu[i][j] = true;//走过的用true表示已经走过↵
dfs(i, j, 1);↵
tu[i][j] = false;//递归回来后将其再次标记为未走过↵
}↵
}↵
cout << sum << endl;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:tczzz,2021-03-13]↵
↵
[tutorial:319429E]↵
↵
Written by:[user:tczzz,2021-03-14]↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define ll long long↵
int tree[110000][20];↵
int n, m;↵
struct node {↵
int i;↵
int j;↵
};↵
queue<node> q;↵
bool f = 0;↵
↵
void bfs() {↵
while (!q.empty()) {↵
node s = q.front();↵
q.pop();↵
if (!f) {↵
cout << tree[s.i][s.j];↵
f = 1;↵
} else {↵
cout << ' ' << tree[s.i][s.j];↵
}↵
if (s.j * 2 <= (1 << m) - 1) {↵
node nw;↵
nw.i = s.i;↵
nw.j = s.j * 2;↵
q.push(nw);↵
}↵
if (s.j * 2 + 1 <= (1 << m) - 1) {↵
node nw;↵
nw.i = s.i;↵
nw.j = s.j * 2 + 1;↵
q.push(nw);↵
}↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
int w;↵
cin >> n >> m;↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= (1 << m) - 1; j++) {↵
cin >> tree[i][j];↵
}↵
}↵
for (int i = 1; i <= n; i <<= 1) {↵
for (int j = i; j < i << 1 && j <= n; j++) {//把每层“节点”的第一个节点扔到队列↵
node s;↵
s.i = j;↵
s.j = 1;↵
q.push(s);↵
}↵
bfs();//一层的节点扔完后进行bfs↵
}↵
cout << endl;↵
return 0;↵
}↵
~~~~~↵
↵
Written by:[user:Visors,2021-03-14]↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int n, m;↵
vector<vector<int> > v;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr), cout.tie(nullptr);↵
cin >> n >> m;↵
v.resize(n, vector<int>(pow(2, m) - 1));↵
for (auto &i : v)↵
for (int &j : i)↵
cin >> j;↵
int depth = log2(n);↵
bool first = true;↵
for (int i = 0; i < depth; i++) {↵
for (int j = 0; j < m; j++) {↵
for (int k = pow(2, i); k < min((int) pow(2, i + 1), n + 1); k++) {↵
for (int t = pow(2, j); t < pow(2, j + 1); t++) {↵
if (first) {↵
cout << v[k - 1][t - 1];↵
first = false;↵
} else cout << ' ' << v[k - 1][t - 1];↵
}↵
}↵
}↵
}↵
cout << endl;↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:rainbu5,2021-03-13]↵
↵
[tutorial:319429F]↵
↵
↵
~~~~~↵
#include<bits/stdc++.h> ↵
↵
using namespace std; ↵
typedef long long ll; ↵
const int N = 100000 + 5 ; ↵
char str[N]; ↵
int main() ↵
{ ↵
//freopen("in.txt","r",stdin); ↵
scanf("%s",str); ↵
int len = strlen(str); ↵
int res = 0 ; ↵
stack <int> st; ↵
for(int i = 0 ;i < len ; i ++) { ↵
char c = str[i] ; ↵
if(st.size() && c == ']' && str[st.top()]=='[')st.pop(); ↵
else if(st.size() && c == '}' && str[st.top()]=='{')st.pop(); ↵
else if(st.size() && c == ')' && str[st.top()]=='(')st.pop(); ↵
else st.push(i); ↵
↵
if(st.size())res = max(res,i - st.top()); ↵
else res = max(res , i + 1); ↵
} ↵
printf("%d",res); ↵
return 0; ↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:SCUEC_Lyh,2021-03-13]↵
↵
[tutorial:319429G]↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define ENDL "\n"↵
typedef long long ll;↵
const int maxn = 2050;↵
const int Mod = 1e9 + 7;↵
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};↵
↵
int n, m;↵
int a[maxn][maxn];↵
ll d[maxn][maxn];↵
bool vis[maxn][maxn];↵
↵
bool check(int r, int c) {↵
if (r <= 0 || c <= 0 || r > n || c > m) return 0;↵
return 1;↵
}↵
↵
void dfs(int x, int y) {↵
vis[x][y] = 1;↵
for (int i = 0, r, c; i < 4; i++) {↵
r = x + dx[i], c = y + dy[i];↵
if (!check(r, c)) continue;↵
if (!vis[r][c] && a[r][c] > a[x][y]) dfs(r, c);↵
if (a[r][c] > a[x][y]) d[x][y] = (d[x][y] + d[r][c]) % Mod;↵
}↵
}↵
↵
int main() {↵
//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
scanf("%d%d", &n, &m);↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= m; j++) {↵
scanf("%d", &a[i][j]);↵
vis[i][j] = 0;↵
}↵
}↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= m; j++) {↵
int cnt = 0;↵
for (int k = 0, r, c; k < 4; k++) {↵
r = i + dx[k], c = j + dy[k];↵
if (check(r, c) && a[r][c] > a[i][j]) cnt++;↵
}↵
d[i][j] = (cnt == 0 ? 1 : 0); //d数组的初始化↵
}↵
}↵
ll ans = 0;↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= m; j++) {↵
if (!vis[i][j]) dfs(i, j); //每个点只访问一次，那么访问过的点就无需再搜↵
ans = (ans + d[i][j]) % Mod;↵
}↵
}↵
printf("%lld\n", ans);↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:lancee,2021-03-13]↵
↵
[tutorial:319429H]↵
↵
↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<cmath>↵
#include<cstring>↵
#include<queue>↵
↵
using namespace std;↵
↵
int n, m, sum, ans;↵
char maze[1005][1005];↵
bool vis[1005][1005];↵
int odddis[6][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {-1,-1}, {1,-1}};↵
int evendis[6][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {-1,1}, {1,1}};↵
↵
↵
struct point {↵
int x;↵
int y;↵
};↵
↵
int gcd(int a, int b) {↵
return b > 0 ? gcd(b, a % b) : a;↵
}↵
↵
bool judge;↵
↵
void bfs(int x, int y) {↵
queue<point> que;↵
int cnt = 0;↵
if (!vis[x][y]) {↵
point pos;↵
pos.x = x;↵
pos.y = y;↵
if (maze[x][y] == '*') {↵
judge = true;↵
}↵
vis[x][y] = true;↵
cnt++;↵
que.push(pos);↵
while (!que.empty()) {↵
if (que.front().x % 2 == 0) {↵
for (int i = 0; i < 6; i++) {↵
int xx = que.front().x + odddis[i][0];↵
int yy = que.front().y + odddis[i][1];↵
if (xx >= 0 && yy >= 0 && xx < n && yy < m↵
&& maze[xx][yy] != '#' && !vis[xx][yy]) {↵
point temp;↵
temp.x = xx;↵
temp.y = yy;↵
que.push(temp);↵
vis[xx][yy] = true;↵
cnt++;↵
if (maze[xx][yy] == '*')↵
judge = true;↵
}↵
}↵
} else if (que.front().x % 2 == 1) {↵
for (int i = 0; i < 6; i++) {↵
int xx = que.front().x + evendis[i][0];↵
int yy = que.front().y + evendis[i][1];↵
if (xx >= 0 && yy >= 0 && xx < n && yy < m↵
&& maze[xx][yy] != '#' && !vis[xx][yy]) {↵
point temp;↵
temp.x = xx;↵
temp.y = yy;↵
que.push(temp);↵
vis[xx][yy] = true;↵
cnt++;↵
if (maze[xx][yy] == '*')↵
judge = true;↵
}↵
}↵
}↵
que.pop();↵
}↵
}↵
//cout << cnt << endl;↵
if (judge == true)sum += cnt;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
int t;↵
cin >> t;↵
while (t--) {↵
ans = 0;↵
sum = 0;↵
cin >> n >> m;↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
cin >> maze[i][j];↵
if (maze[i][j] == '.' || maze[i][j] == '*')↵
ans++;↵
}↵
}↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
if (maze[i][j] != '#' && !vis[i][j]) {↵
judge = false;↵
bfs(i, j);↵
}↵
}↵
}↵
int num = gcd(ans, sum);↵
if (sum == 0)↵
cout << 0 << endl;↵
else if (sum == num)↵
cout << 1 << endl;↵
else↵
cout << sum / num << "/" << ans / num << endl;↵
memset(vis, 0, sizeof(vis));↵
}↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:Visors,2021-03-13]↵
↵
粗暴复刻了↵
[problem:1345C]↵
↵
[tutorial:319429I]↵
↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr), cout.tie(nullptr);↵
int T;↵
cin >> T;↵
while (T--) {↵
int n;↵
cin >> n;↵
vector<int> v(n);↵
vector<bool> book(n);↵
for (int &it:v) cin >> it;↵
for (int i = 0, tmp; i < n; i++) {↵
tmp = (((v[i] + i) % n) + n) % n; //避免%出负数↵
if (!book[tmp]) book[tmp] = true;↵
else {↵
cout << "YES" << endl;↵
goto over;↵
}↵
}↵
cout << "NO" << endl;↵
over:;↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:twh12138,2021-03-13]↵
↵
[tutorial:319429J]↵
↵
↵
~~~~~↵
#include<iostream>↵
#include<queue>↵
#include<cstring>↵
↵
using namespace std;↵
↵
const int N = 2e5 + 10;↵
↵
int dis[N];↵
int n,k;↵
↵
queue<int> q;↵
↵
int bfs()↵
{↵
memset(dis,-1,sizeof dis);↵
q.push(n);↵
dis[n] = 0;↵
↵
while(q.size())↵
{↵
int t = q.front();↵
q.pop();↵
↵
if(t == k) return dis[t];↵
↵
if(t + 1 <= N && dis[t + 1] == -1)↵
{↵
q.push(t + 1);↵
dis[t + 1] = dis[t] + 1;↵
}↵
if(t - 1 >= 0 && dis[t - 1] == -1)↵
{↵
q.push(t - 1);↵
dis[t - 1] = dis[t] + 1;↵
}↵
if(t * 2 <= N && dis[2 * t] == -1)↵
{↵
q.push(2 * t);↵
dis[2 * t] = dis[t] + 1;↵
}↵
}↵
↵
return 0;↵
}↵
↵
int main()↵
{↵
cin >> n >> k;↵
cout << bfs() << endl;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:CofDoria,2021-03-13]↵
↵
[tutorial:319429K]↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define rep(l, a, b) for (ll l = a; l < b; ++l)↵
↵
int t, n;↵
ll ans = 0;↵
↵
struct node {↵
ll t, val;↵
node() { t = 0, val = 0; }↵
} a[1500005];↵
↵
bool cmp(node x, node y) {↵
if (x.t == y.t) return x.val > y.val;↵
return x.t < y.t;↵
}↵
↵
priority_queue<int, vector<int>, greater<int> > q;↵
↵
int main() {↵
cin >> n;↵
rep(i, 0, n) cin >> a[i].t >> a[i].val;↵
sort(a, a + n, cmp);↵
rep(i, 0, n) {↵
if (i && a[i].t == a[i - 1].t) { ↵
if (q.size() < a[i].t) {↵
q.push(a[i].val);↵
ans += a[i].val;↵
} else if (q.top() < a[i].val) {↵
ans += a[i].val - q.top();↵
q.pop();↵
q.push(a[i].val);↵
}↵
} else {↵
ans += a[i].val;↵
q.push(a[i].val);↵
}↵
}↵
cout << ans + 5;↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:lqrs,2021-03-13]↵
↵
[tutorial:319429L]↵
↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <iterator>↵
↵
using namespace std;↵
↵
#define N 10005↵
vector<int> edge[N]; //二维数组↵
int res = 0;↵
↵
void dfs(int step, int pos, int prepos) {↵
if (step == 3) {↵
++res;↵
return;↵
}↵
if (edge[pos].size()) {↵
vector<int>::iterator it;↵
for (it = edge[pos].begin(); it != edge[pos].end(); ++it)↵
if (*it != prepos) dfs(step + 1, *it, pos);↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cout.tie(NULL);↵
int n, m, U, V;↵
cin >> n >> m;↵
for (int i = 0; i < m; ++i) {↵
cin >> U >> V;↵
edge[U].push_back(V);↵
edge[V].push_back(U);↵
}↵
for (int i = 1; i <= n; ++i) dfs(0, i, 0);↵
cout << res << endl;↵
return 0;↵
}↵
~~~~~
[contest:319429]↵
↵
Idea:[user:aabbccSu,2021-03-13]↵
↵
[tutorial:319429A]↵
↵
↵
Idea:[user:SHIYAOHUA,2021-03-13]↵
↵
[tutorial:319429B]↵
↵
------↵
↵
Idea:[user:waswasqq,2021-03-13]↵
↵
[tutorial:319429C]↵
↵
------↵
↵
Idea:[user:hushnow,2021-03-13]↵
↵
[tutorial:319429D]↵
↵
------↵
↵
Idea:[user:tczzz,2021-03-13]↵
↵
[tutorial:319429E]↵
↵
------↵
↵
Idea:[user:rainbu5,2021-03-13]↵
↵
[tutorial:319429F]↵
↵
------↵
↵
Idea:[user:SCUEC_Lyh,2021-03-13]↵
↵
[tutorial:319429G]↵
↵
------↵
↵
Idea:[user:lancee,2021-03-13]↵
↵
[tutorial:319429H]↵
↵
------↵
↵
Idea:[user:Visors,2021-03-13]↵
↵
粗暴复刻了↵
[problem:1345C]↵
↵
[tutorial:319429I]↵
↵
------↵
↵
Idea:[user:twh12138,2021-03-13]↵
↵
[tutorial:319429J]↵
↵
------↵
↵
Idea:[user:CofDoria,2021-03-13]↵
↵
[tutorial:319429K]↵
↵
------↵
↵
Idea:[user:lqrs,2021-03-13]↵
↵
[tutorial:319429L]
~~~~~↵
#include <bits/stdc++.h>↵
#include <unordered_map>↵
↵
using namespace std;↵
#define ENDL "\n"↵
#define lowbit(x) (x & (-x))↵
typedef long long ll;↵
typedef long double ld;↵
typedef unsigned long long ull;↵
typedef pair<int, int> pii;↵
typedef pair<ll, ll> pll;↵
typedef pair<double, double> pdd;↵
const double eps = 1e-8;↵
const double pi = acos(-1.0);↵
const int inf = 0x3f3f3f3f;↵
const double dinf = 1e300;↵
const ll INF = 1e18;↵
const int Mod = 1e9 + 7;↵
const int maxn = 2e5 + 10;↵
↵
bool isLeap(int x) {↵
if ((x % 4 == 0 && x % 100) || x % 400 == 0) return 1;↵
return 0;↵
}↵
↵
↵
int p[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};↵
int q[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};↵
int v[] = {0, 1, 2, 4, 8, 16, 32};↵
↵
//2021/1/1 Friday↵
int getWeek(int Y, int M, int D) {↵
int y = 2021, m = 1, d = 1, w = 5;↵
while (y != Y || m != M || d != D) {↵
if (!isLeap(y)) {↵
if (d + 1 > p[m]) {↵
if (m + 1 > 12) y++, m = 1, d = 1;↵
else {↵
m++;↵
d = 1;↵
}↵
} else d++;↵
} else {↵
if (d + 1 > q[m]) {↵
if (m + 1 > 12) y++, m = 1, d = 1;↵
else {↵
m++;↵
d = 1;↵
}↵
} else d++;↵
}↵
↵
w = w + 1 > 7 ? 1 : w + 1;↵
}↵
return w;↵
}↵
↵
int solve(int y, int m, int d, int w, int Y, int M, int D) {↵
int ans = 0;↵
while (y != Y || m != M || d != D) {↵
if (!isLeap(y)) {↵
if (d + 1 > p[m]) {↵
if (m + 1 > 12) y++, m = 1, d = 1;↵
else {↵
m++;↵
d = 1;↵
}↵
} else d++;↵
} else {↵
if (d + 1 > q[m]) {↵
if (m + 1 > 12) y++, m = 1, d = 1;↵
else {↵
m++;↵
d = 1;↵
}↵
} else d++;↵
}↵
if (w < 7) ans += v[w];↵
else ans /= 2;↵
w = w + 1 > 7 ? 1 : w + 1;↵
}↵
if (w < 7) ans += v[w];↵
else ans /= 2;↵
return ans;↵
}↵
↵
//首先计算出起始天是周几，然后向后模拟↵
int main() {↵
//freopen("in.txt","r",stdin);↵
//freopen("out.txt","w",stdout);↵
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);↵
int T;↵
int y1, m1, d1, y2, m2, d2;↵
cin >> T;↵
while (T--) {↵
cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;↵
int now = getWeek(y1, m1, d1);↵
cout << solve(y1, m1, d1, now, y2, m2, d2) << ENDL;↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:SHIYAOHUA,2021-03-13]↵
↵
[tutorial:319429B]↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define ENDL "\n"↵
↵
char s[20];↵
↵
int main() {↵
int T, n;↵
scanf("%d", &T);↵
while (T--) {↵
scanf("%d", &n);↵
double sum = 0.0;↵
int cnt = 0;↵
for (int i = 1; i <= n; i++) {↵
scanf("%s", s);↵
if (isalpha(s[0])) continue;↵
else {↵
sum += atof(s), cnt++;↵
}↵
}↵
if (cnt == 0) puts("0");↵
else printf("%.10lf\n", sum / cnt);↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:waswasqq,2021-03-13]↵
↵
[tutorial:319429C]↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
typedef long long ll;↵
const int mod = 1e9 + 7;↵
↵
int main() {↵
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);↵
int t;↵
//scanf("%d",&t);↵
cin >> t;↵
while (t--) {↵
int n;;↵
//scanf("%d",&n);↵
cin >> n;↵
ll sum = 0;↵
for (int i = 0; i < n; i++) {↵
int x;↵
//scanf("%d",&x);↵
cin >> x;↵
sum += x;↵
sum %= mod;↵
}↵
n--;↵
while (n--)//也可以手写快速幂↵
{↵
sum *= 2;↵
sum %= mod;↵
}↵
//printf("%d\n",sum);↵
cout << sum << '\n';↵
}↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:hushnow,2021-03-13]↵
↵
[tutorial:319429D]↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
#define ll long long↵
int n, m;↵
int dx[] = {0, 1, 0, -1};↵
int dy[] = {-1, 0, 1, 0};//方向数组↵
bool tu[5][5];//表示是否走过↵
int sum = 0;↵
↵
void dfs(int x, int y, int num)//x，y是当前到的格子，num是当前已经排了的蛇的长度↵
{↵
if (num == m)//当排到蛇的长度为m时即可认为是一种情况，并sum++↵
{↵
sum++;↵
return;↵
}↵
for (int i = 0; i < 4; i++) {↵
if (x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < n && (!tu[x + dx[i]][y + dy[i]])) {↵
tu[x + dx[i]][y + dy[i]] = true;//走过的用true表示已经走过↵
dfs(x + dx[i], y + dy[i], num + 1);↵
tu[x + dx[i]][y + dy[i]] = false;//递归回来后将其再次标记为未走过↵
}↵
}↵
}↵
↵
int main() {↵
cin >> n >> m;↵
memset(tu, false, sizeof(tu));//将图表示为都没有走过↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < n; j++) {↵
tu[i][j] = true;//走过的用true表示已经走过↵
dfs(i, j, 1);↵
tu[i][j] = false;//递归回来后将其再次标记为未走过↵
}↵
}↵
cout << sum << endl;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:tczzz,2021-03-13]↵
↵
[tutorial:319429E]↵
↵
Written by:[user:tczzz,2021-03-14]↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define ll long long↵
int tree[110000][20];↵
int n, m;↵
struct node {↵
int i;↵
int j;↵
};↵
queue<node> q;↵
bool f = 0;↵
↵
void bfs() {↵
while (!q.empty()) {↵
node s = q.front();↵
q.pop();↵
if (!f) {↵
cout << tree[s.i][s.j];↵
f = 1;↵
} else {↵
cout << ' ' << tree[s.i][s.j];↵
}↵
if (s.j * 2 <= (1 << m) - 1) {↵
node nw;↵
nw.i = s.i;↵
nw.j = s.j * 2;↵
q.push(nw);↵
}↵
if (s.j * 2 + 1 <= (1 << m) - 1) {↵
node nw;↵
nw.i = s.i;↵
nw.j = s.j * 2 + 1;↵
q.push(nw);↵
}↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
int w;↵
cin >> n >> m;↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= (1 << m) - 1; j++) {↵
cin >> tree[i][j];↵
}↵
}↵
for (int i = 1; i <= n; i <<= 1) {↵
for (int j = i; j < i << 1 && j <= n; j++) {//把每层“节点”的第一个节点扔到队列↵
node s;↵
s.i = j;↵
s.j = 1;↵
q.push(s);↵
}↵
bfs();//一层的节点扔完后进行bfs↵
}↵
cout << endl;↵
return 0;↵
}↵
~~~~~↵
↵
Written by:[user:Visors,2021-03-14]↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int n, m;↵
vector<vector<int> > v;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr), cout.tie(nullptr);↵
cin >> n >> m;↵
v.resize(n, vector<int>(pow(2, m) - 1));↵
for (auto &i : v)↵
for (int &j : i)↵
cin >> j;↵
int depth = log2(n);↵
bool first = true;↵
for (int i = 0; i < depth; i++) {↵
for (int j = 0; j < m; j++) {↵
for (int k = pow(2, i); k < min((int) pow(2, i + 1), n + 1); k++) {↵
for (int t = pow(2, j); t < pow(2, j + 1); t++) {↵
if (first) {↵
cout << v[k - 1][t - 1];↵
first = false;↵
} else cout << ' ' << v[k - 1][t - 1];↵
}↵
}↵
}↵
}↵
cout << endl;↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:rainbu5,2021-03-13]↵
↵
[tutorial:319429F]↵
↵
↵
~~~~~↵
#include<bits/stdc++.h> ↵
↵
using namespace std; ↵
typedef long long ll; ↵
const int N = 100000 + 5 ; ↵
char str[N]; ↵
int main() ↵
{ ↵
//freopen("in.txt","r",stdin); ↵
scanf("%s",str); ↵
int len = strlen(str); ↵
int res = 0 ; ↵
stack <int> st; ↵
for(int i = 0 ;i < len ; i ++) { ↵
char c = str[i] ; ↵
if(st.size() && c == ']' && str[st.top()]=='[')st.pop(); ↵
else if(st.size() && c == '}' && str[st.top()]=='{')st.pop(); ↵
else if(st.size() && c == ')' && str[st.top()]=='(')st.pop(); ↵
else st.push(i); ↵
↵
if(st.size())res = max(res,i - st.top()); ↵
else res = max(res , i + 1); ↵
} ↵
printf("%d",res); ↵
return 0; ↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:SCUEC_Lyh,2021-03-13]↵
↵
[tutorial:319429G]↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define ENDL "\n"↵
typedef long long ll;↵
const int maxn = 2050;↵
const int Mod = 1e9 + 7;↵
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};↵
↵
int n, m;↵
int a[maxn][maxn];↵
ll d[maxn][maxn];↵
bool vis[maxn][maxn];↵
↵
bool check(int r, int c) {↵
if (r <= 0 || c <= 0 || r > n || c > m) return 0;↵
return 1;↵
}↵
↵
void dfs(int x, int y) {↵
vis[x][y] = 1;↵
for (int i = 0, r, c; i < 4; i++) {↵
r = x + dx[i], c = y + dy[i];↵
if (!check(r, c)) continue;↵
if (!vis[r][c] && a[r][c] > a[x][y]) dfs(r, c);↵
if (a[r][c] > a[x][y]) d[x][y] = (d[x][y] + d[r][c]) % Mod;↵
}↵
}↵
↵
int main() {↵
//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
scanf("%d%d", &n, &m);↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= m; j++) {↵
scanf("%d", &a[i][j]);↵
vis[i][j] = 0;↵
}↵
}↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= m; j++) {↵
int cnt = 0;↵
for (int k = 0, r, c; k < 4; k++) {↵
r = i + dx[k], c = j + dy[k];↵
if (check(r, c) && a[r][c] > a[i][j]) cnt++;↵
}↵
d[i][j] = (cnt == 0 ? 1 : 0); //d数组的初始化↵
}↵
}↵
ll ans = 0;↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= m; j++) {↵
if (!vis[i][j]) dfs(i, j); //每个点只访问一次，那么访问过的点就无需再搜↵
ans = (ans + d[i][j]) % Mod;↵
}↵
}↵
printf("%lld\n", ans);↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:lancee,2021-03-13]↵
↵
[tutorial:319429H]↵
↵
↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<cmath>↵
#include<cstring>↵
#include<queue>↵
↵
using namespace std;↵
↵
int n, m, sum, ans;↵
char maze[1005][1005];↵
bool vis[1005][1005];↵
int odddis[6][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {-1,-1}, {1,-1}};↵
int evendis[6][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}, {-1,1}, {1,1}};↵
↵
↵
struct point {↵
int x;↵
int y;↵
};↵
↵
int gcd(int a, int b) {↵
return b > 0 ? gcd(b, a % b) : a;↵
}↵
↵
bool judge;↵
↵
void bfs(int x, int y) {↵
queue<point> que;↵
int cnt = 0;↵
if (!vis[x][y]) {↵
point pos;↵
pos.x = x;↵
pos.y = y;↵
if (maze[x][y] == '*') {↵
judge = true;↵
}↵
vis[x][y] = true;↵
cnt++;↵
que.push(pos);↵
while (!que.empty()) {↵
if (que.front().x % 2 == 0) {↵
for (int i = 0; i < 6; i++) {↵
int xx = que.front().x + odddis[i][0];↵
int yy = que.front().y + odddis[i][1];↵
if (xx >= 0 && yy >= 0 && xx < n && yy < m↵
&& maze[xx][yy] != '#' && !vis[xx][yy]) {↵
point temp;↵
temp.x = xx;↵
temp.y = yy;↵
que.push(temp);↵
vis[xx][yy] = true;↵
cnt++;↵
if (maze[xx][yy] == '*')↵
judge = true;↵
}↵
}↵
} else if (que.front().x % 2 == 1) {↵
for (int i = 0; i < 6; i++) {↵
int xx = que.front().x + evendis[i][0];↵
int yy = que.front().y + evendis[i][1];↵
if (xx >= 0 && yy >= 0 && xx < n && yy < m↵
&& maze[xx][yy] != '#' && !vis[xx][yy]) {↵
point temp;↵
temp.x = xx;↵
temp.y = yy;↵
que.push(temp);↵
vis[xx][yy] = true;↵
cnt++;↵
if (maze[xx][yy] == '*')↵
judge = true;↵
}↵
}↵
}↵
que.pop();↵
}↵
}↵
//cout << cnt << endl;↵
if (judge == true)sum += cnt;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
int t;↵
cin >> t;↵
while (t--) {↵
ans = 0;↵
sum = 0;↵
cin >> n >> m;↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
cin >> maze[i][j];↵
if (maze[i][j] == '.' || maze[i][j] == '*')↵
ans++;↵
}↵
}↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j < m; j++) {↵
if (maze[i][j] != '#' && !vis[i][j]) {↵
judge = false;↵
bfs(i, j);↵
}↵
}↵
}↵
int num = gcd(ans, sum);↵
if (sum == 0)↵
cout << 0 << endl;↵
else if (sum == num)↵
cout << 1 << endl;↵
else↵
cout << sum / num << "/" << ans / num << endl;↵
memset(vis, 0, sizeof(vis));↵
}↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:Visors,2021-03-13]↵
↵
粗暴复刻了↵
[problem:1345C]↵
↵
[tutorial:319429I]↵
↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr), cout.tie(nullptr);↵
int T;↵
cin >> T;↵
while (T--) {↵
int n;↵
cin >> n;↵
vector<int> v(n);↵
vector<bool> book(n);↵
for (int &it:v) cin >> it;↵
for (int i = 0, tmp; i < n; i++) {↵
tmp = (((v[i] + i) % n) + n) % n; //避免%出负数↵
if (!book[tmp]) book[tmp] = true;↵
else {↵
cout << "YES" << endl;↵
goto over;↵
}↵
}↵
cout << "NO" << endl;↵
over:;↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:twh12138,2021-03-13]↵
↵
[tutorial:319429J]↵
↵
↵
~~~~~↵
#include<iostream>↵
#include<queue>↵
#include<cstring>↵
↵
using namespace std;↵
↵
const int N = 2e5 + 10;↵
↵
int dis[N];↵
int n,k;↵
↵
queue<int> q;↵
↵
int bfs()↵
{↵
memset(dis,-1,sizeof dis);↵
q.push(n);↵
dis[n] = 0;↵
↵
while(q.size())↵
{↵
int t = q.front();↵
q.pop();↵
↵
if(t == k) return dis[t];↵
↵
if(t + 1 <= N && dis[t + 1] == -1)↵
{↵
q.push(t + 1);↵
dis[t + 1] = dis[t] + 1;↵
}↵
if(t - 1 >= 0 && dis[t - 1] == -1)↵
{↵
q.push(t - 1);↵
dis[t - 1] = dis[t] + 1;↵
}↵
if(t * 2 <= N && dis[2 * t] == -1)↵
{↵
q.push(2 * t);↵
dis[2 * t] = dis[t] + 1;↵
}↵
}↵
↵
return 0;↵
}↵
↵
int main()↵
{↵
cin >> n >> k;↵
cout << bfs() << endl;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:CofDoria,2021-03-13]↵
↵
[tutorial:319429K]↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define rep(l, a, b) for (ll l = a; l < b; ++l)↵
↵
int t, n;↵
ll ans = 0;↵
↵
struct node {↵
ll t, val;↵
node() { t = 0, val = 0; }↵
} a[1500005];↵
↵
bool cmp(node x, node y) {↵
if (x.t == y.t) return x.val > y.val;↵
return x.t < y.t;↵
}↵
↵
priority_queue<int, vector<int>, greater<int> > q;↵
↵
int main() {↵
cin >> n;↵
rep(i, 0, n) cin >> a[i].t >> a[i].val;↵
sort(a, a + n, cmp);↵
rep(i, 0, n) {↵
if (i && a[i].t == a[i - 1].t) { ↵
if (q.size() < a[i].t) {↵
q.push(a[i].val);↵
ans += a[i].val;↵
} else if (q.top() < a[i].val) {↵
ans += a[i].val - q.top();↵
q.pop();↵
q.push(a[i].val);↵
}↵
} else {↵
ans += a[i].val;↵
q.push(a[i].val);↵
}↵
}↵
cout << ans + 5;↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
------↵
↵
Idea:[user:lqrs,2021-03-13]↵
↵
[tutorial:319429L]↵
↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <iterator>↵
↵
using namespace std;↵
↵
#define N 10005↵
vector<int> edge[N]; //二维数组↵
int res = 0;↵
↵
void dfs(int step, int pos, int prepos) {↵
if (step == 3) {↵
++res;↵
return;↵
}↵
if (edge[pos].size()) {↵
vector<int>::iterator it;↵
for (it = edge[pos].begin(); it != edge[pos].end(); ++it)↵
if (*it != prepos) dfs(step + 1, *it, pos);↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cout.tie(NULL);↵
int n, m, U, V;↵
cin >> n >> m;↵
for (int i = 0; i < m; ++i) {↵
cin >> U >> V;↵
edge[U].push_back(V);↵
edge[V].push_back(U);↵
}↵
for (int i = 1; i <= n; ++i) dfs(0, i, 0);↵
cout << res << endl;↵
return 0;↵
}↵
~~~~~
