比赛传送门： [contest:319429]
Idea:aabbccSu
Tutorial is loading...
#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:SHIYAOHUA
Tutorial is loading...
#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:waswasqq
Tutorial is loading...
#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:hushnow
Tutorial is loading...
#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:tczzz
Tutorial is loading...
Written by:tczzz
#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:Visors
#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:rainbu5
Tutorial is loading...
#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:Lian
Tutorial is loading...
#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:lancee
Tutorial is loading...
#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:Visors
粗暴复刻了 1345C - Hilbert's Hotel
Tutorial is loading...
#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:twh12138
Tutorial is loading...
#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:CofDoria
Tutorial is loading...
#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:lqrs
Tutorial is loading...
#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;
}
