❥这次秋季赛查重后有效提交队伍共1000余队，前5%金，10%银，20%铜，冠军1名，亚军2名，季军3名。每次比赛之余都不得不感慨oier的可怕实力和某些竞赛强省的高端水平。
❥赛时一直稳定在前5%（金奖行列），一度干到第七，傻瓜式地读错题加了罚时，最后开了A题，600多行代码超时了，短时间内想不到好的解决方案，最终gg辽~ 没能拿到季军的奖牌.
❥总体感觉不错，C题（几何题）提交AC后，队友说数据有点水，不然可能过不了，但由于在比赛冲奖，就没有多看。其他题还好，几乎没有什么太大的失误。A题可惜没能做出来，因为没有做对就没贴上来，后来账号登不上，连代码都看不到了... 就有点迷
❥比赛一开始先切了F题、然后队友跟榜看J题，说题意有点迷，就帮他一起读了一下，避免了罚时。接着切了B题，没睡醒RE了一次，队友这时在看D题，我去做了C，AC后冲到15名，这时候其实保不了金的，毕竟比赛才进行一个小时左右，只能继续做...
❥具体的过程在下面了，前面就不再啰嗦了hh
目录
☀️| B-二进制
⭐️题面
⭐️题解
⭐️代码
☀️| C-不正方形
⭐️题面
⭐️题解
⭐️代码
☀️| D-分配颜色
⭐️题面
⭐️题解
⭐️代码
☀️| E-土地规划
⭐️题面
⭐️题解
⭐️代码
☀️| F-CTF
⭐️题面
⭐️题解
⭐️代码
☀️| G-希望
⭐️题面
⭐️题解
⭐️代码
☀️| I-排队队
⭐️题面
⭐️题解
⭐️代码
☀️| J-抽奖
⭐️题面
⭐️题解
⭐️代码
☀️| B-二进制
⭐️题面
⭐️题解
build tree，根据op的值判断要 modify 还是 query，做出具体的操作模拟实现
⭐️代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, q, a[N];struct Node{int l, r;ll sum, lazy;
}tree[11][N << 2];void pushup(int id, int pos)
{tree[id][pos].sum = tree[id][pos << 1].sum + tree[id][pos << 1 | 1].sum;
}void pushdown(int id, int pos)
{auto &root = tree[id][pos], &left = tree[id][pos << 1], &right = tree[id][pos << 1 | 1];if (root.lazy){left.sum += 1LL * (left.r - left.l + 1) * root.lazy;right.sum += 1LL * (right.r - right.l + 1) * root.lazy;left.lazy += root.lazy, right.lazy += root.lazy;root.lazy = 0;}
}
void build(int id, int pos, int l, int r)
{tree[id][pos] = {l, r, 0, 0};if (l == r){tree[id][pos] = {l, l, a[l], 0};return;}int mid = l + r >> 1;build(id, pos << 1, l, mid);build(id, pos << 1 | 1, mid + 1, r);pushup(id, pos);
}void modify(int id, int pos, int l, int r, int val)
{if (l <= tree[id][pos].l && tree[id][pos].r <= r){tree[id][pos].sum += 1LL * (tree[id][pos].r - tree[id][pos].l + 1) * val;tree[id][pos].lazy += val;return;}pushdown(id, pos);int mid = tree[id][pos].l + tree[id][pos].r >> 1;if (l <= mid) modify(id, pos << 1, l, r, val);if (mid < r) modify(id, pos << 1 | 1, l, r, val);pushup(id, pos);
}ll query(int id, int pos, int l, int r)
{if (l <= tree[id][pos].l && tree[id][pos].r <= r) return tree[id][pos].sum;pushdown(id, pos);int mid = tree[id][pos].l + tree[id][pos].r >> 1;ll sum = 0;if (l <= mid) sum += query(id, pos << 1, l, r);if (mid < r) sum += query(id, pos << 1 | 1, l, r);return sum;
}int main()
{scanf("%d %d", &n, &q);for (int i = 0; i <= 10; i++)build(i, 1, 1, n);while (q--){int op; scanf("%d", &op);if (op == 1) {int l, r;int st, val; scanf("%d %d", &st, &l);scanf("%d %d", &r, &val);for (int i = 0; i <= 10; i++) {if ((st >> i) & 1) {modify(i, 1, l, r, val);}}}else {int st; scanf("%d", &st);int l, r; scanf("%d %d", &l, &r);ll ans = 0;for (int i = 0; i <= 10; i++) {if ((st >> i) & 1) ans += query(i, 1, l, r);}printf("%lld\n", ans);}}return 0;
}☀️| C-不正方形
⭐️题面
⭐️题解
- 这是一道几何题，实际上是水数据过的，真正做起来并不算简单，可能几何学的并不好，感觉这题如果数据比较严的话，要考虑到的东西就比较多了，正答率也会下降很多。
- 读完这道题，一开始以为是模板题，但没有对上号就只能手动模拟实现了。本地样例过了以后提交刚好一把过了，赛时就没再纠结。
⭐️代码
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ll long longtemplate<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}struct kk{ll x,y;} a[300];
struct ff{ll x,y;} b[300];map<pair<ll,ll>,ll>s;
map<pair<ll,ll>,ll>q;signed main()
{ll n,m; read(n); read(m);for(int i=1; i<=n; i++) {read(a[i].x); read(a[i].y);s[mp(a[i].x,a[i].y)]=1;}for(int i=1; i<=m; i++) {read(b[i].x); read(b[i].y);q[mp(a[i].x,a[i].y)]=1;}if(n<2||m<2) {printf("NO\n");return 0;}for(int i=1; i<=n; i++){for(int j=i+1; j<=n; j++){if(a[i].x==a[j].x){ll L=0; ll R=0;for(int k=1; k<=m; k++) {if(b[i].x<a[i].x) L++;if(b[i].x>a[i].x) R++;if(L&&R) break;}if(L&&R) {printf("YES\n");return 0;}continue;}double kk=(a[i].y-a[j].y)*1.0/(a[i].x-a[j].x); //kk为1也ACdouble bb=a[i].y-kk*a[i].x;ll LL=0; ll RR=0;for(int k=1; k<=m; k++) {double q=b[k].x*kk+bb;if(q>b[k].y) RR++;if(q<b[k].y) LL++;if(RR&&LL) {printf("YES\n");return 0;}}}}printf("NO\n");
}☀️| D-分配颜色
⭐️题面
⭐️题解
- 一开始觉得是两层dfs，嵌套一下，枚举所有可能，然后符合条件的数累加起来。但可能爆栈，要剪枝。后来发现要用组合数学。
- 这时候在37名，因为mod不是质数，用不了费马小定理。
- 后来队友开玩笑说想用9e6的空间开杨辉三角写，又思考了一会。强调了重点：x个物品分给y个人，y个人互不相同，方案数一共有多少，队友写的是 (y^x)，我提出是C[x+y-1,y]。
- 改完后交了第一发，AC！
⭐️代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3112;
const ll mod = 555555555;ll ksm(ll a, ll p)
{ll res = 1;while (p){if (p & 1) res = res * a % mod;a = a * a % mod;p >>= 1;}return res;
}int c[N][N];
void init()
{for(int i=0; i<N; i++)for(int j=0; j<=i; j++)if(!j) c[i][j] = 1;else c[i][j] = (1LL * c[i-1][j] + c[i-1][j-1]) %mod;
}int main()
{init();int n, m, p, q, t; scanf("%d %d %d %d %d", &n, &m, &p, &q, &t);auto get = [&] (int all, int used, int cnt){ll ans = c[all][used];cnt -= used; cnt /= 2;ans = ans * c[all + cnt - 1][cnt] % mod;return ans;};ll ans = 0;for (int i = 0; i <= n; i++){for (int j = 0; j <= m; j++){if (i > p || j > q) continue;int cnt = i * m + j * n - 2 * i * j;if (cnt != t) continue;if ((p - i) % 2 || (q - j) % 2) continue;ll x = get(n, i, p), y = get(m, j, q);ans = (ans + 1LL * x % mod * y % mod) % mod;}}printf("%lld\n", ans);return 0;
}☀️| E-土地规划
⭐️题面
⭐️题解
妥妥的一道规律题，需要打表找好规律，代码不复杂
⭐️代码
#define ll long long
#define mod 1000000000
#include <bits/stdc++.h>
using namespace std;
#define maxn 500010
char s[100][100];
int sol(ll x,ll y){if(y==1) return 1;if(y>x) return 0;ll ma=0;for(int i=1;i<60;i++){if(x&(1LL<<i)) ma=(1LL<<i);}if(x==ma) return 1;if(y>ma) return sol(x-ma,y-ma);return sol(x-ma,y);
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);ll t,x,y;cin>>t>>x>>y;int n,m;cin>>n>>m;for(ll i=0;i<m;i++){for(ll j=0;j<n;j++){ll nx=j+x,ny=i+y;if((nx+ny)%2) s[i][j]='.';else if(ny>nx) s[i][j]='.';else if((nx+ny)/2+1>t) s[i][j]='.';else{ll ti=(nx+ny)/2+1;char ss='A';if(ti%2==0) ss='B';if(sol(ti,ny+1))s[i][j]=ss;else s[i][j]='.';//cout<<ti<<"__\n";}}}for(int i=m-1;i>=0;i--){for(int j=0;j<n;j++) cout<<s[i][j];cout<<"\n";}return 0;
}☀️| F-CTF
⭐️题面
⭐️题解
签到题，根据题意模拟即可
⭐️代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;int main()
{ll x; scanf("%lld", &x);ll ans = 0, cnt = 1, base = 1;while (x){base <<= 1;ans += cnt * min(base, x);x -= min(base, x);cnt++;}printf("%lld\n", ans);return 0;
}☀️| G-希望
⭐️题面
⭐️题解
一开始写错了一个小细节，最后一个continue那里m和d的大小关系写错了，导致数据范围约束了，后来确定是M<=d，AC~
⭐️代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;int main()
{int n, m; scanf("%d %d", &n, &m);vector<vector<int>> a(n + 1), b(n + 1);for (int i = 1; i < n; i++){int x, y; scanf("%d %d", &x, &y);a[x].push_back(y);a[y].push_back(x);}for (int i = 1; i < n; i++){int x, y; scanf("%d %d", &x, &y);b[x].push_back(y);b[y].push_back(x);}vector<vector<int>> da(n + 1, vector<int>(n + 1));function<void(int, int, int, int)> dfsa = [&] (int id, int u, int f, int d){da[id][u] = d;for (auto x: a[u]){if (x == f) continue;dfsa(id, x, u, d + 1);}};for (int i = 1; i <= n; i++) dfsa(i, i, 0, 0);vector<int> cntb(n + 1);function<void(int, int, int, int)> dfsb = [&] (int id, int u, int f, int d){cntb[d]++;for (auto x: b[u]){if (x == f) continue;dfsb(id, x, u, d + 1);}};for (int i = 1; i <= n; i++) dfsb(i, i, 0, 0);int ans = 0;int fm = n * (n - 1);m -= 2;for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){if (da[i][j] == 0) continue;int d = da[i][j];if (m <= d) continue;ans += cntb[m - d];}}printf("%.4f\n", 1.0 * ans / fm);return 0;
}☀️| I-排队队
⭐️题面
⭐️题解
- 题意抽象出来就是：n个数，a[i]和a[i-1]相同则贡献pi，不同则贡献q[i]，p[i]和q[i]大小不确定。
- 一开始的思路：首先解决的问题是同学之前的排列问题，之后就是排列完成之后的判断，判断条件怎么写。从左到右依次查验pi，qi，然后累加起来。每排列一次，更新依次max的值。
- 感觉是数论题，不是自己擅长的领域...后来把题意告诉队友去做了。
⭐️代码
#define ll long long
#define mod 1000000000
#include <bits/stdc++.h>
using namespace std;
#define maxn 500010
vector<pair<int,int>>b[maxn];using namespace std;
bool cmp(pair<int,int>p,pair<int,int>q){return p.second-p.first<q.second-q.first;
}
struct cv{int x,y;bool friend operator<(cv p,cv q){return p.y<q.y;}
};
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin>>n;while(n--){int x,y,z;cin>>x>>y>>z;b[x].push_back({y,z});}vector<vector<pair<int,int>>>vv;int ans=0;for(int i=0;i<maxn;i++){if(b[i].size()==0) continue;int fl=0;vector<pair<int,int>>v;int sum=0;for(auto j:b[i]){if(j.first<=j.second){fl=1;v.push_back(j);}else sum+=j.first;}int las=0;if(fl==0){for(int j=1;j<b[i].size();j++){if(b[i][j].first-b[i][j].second<b[i][las].first-b[i][las].second) las=j;}sum-=b[i][las].first;v.push_back(b[i][las]);}ans+=sum;sort(v.begin(),v.end(),cmp);vv.push_back(v);}int ctsum=0,ma=0;for(int i=0;i<vv.size();i++){ma=max(ma,(int)vv[i].size());ctsum+=vv[i].size();}if(ma>ctsum-ma+1){for(int i=0;i<vv.size();i++){if(vv[i].size()!=ma){for(auto j:vv[i]) ans+=j.second;}else{int res=ctsum-ma+1;while(!vv[i].empty()){if(res>0){res--;ans+=vv[i].back().second;}else ans+=vv[i].back().first;vv[i].pop_back();}}}}else{for(int i=0;i<vv.size();i++) {for (auto j:vv[i]) ans += j.second;}}cout<<ans;return 0;
}☀️| J-抽奖
⭐️题面
⭐️题解
- 题目可能有点迷惑，这时候就要把题意抽象，提取出来。
- 举个例子说明就是：第一轮1~9没满（9次），十连触发就在第二轮10~19里面触发了（10次），本来应该是第10次触发的，但是第一轮没抽满10次。
- 如果单抽一次（第20次），也能得到 3星辉。
- 按照这个去写就没什么问题了，毕竟是签到题。
⭐️代码
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 2e5 + 10;int main()
{ll x; scanf("%lld", &x);ll y = 0, ans = x / 160;y = ans / 10 * 3;ll res = 10 - ans % 10;while (y > 5){ll tmp = y / 5;ans += tmp;ll ny = 0;if (tmp >= res) ny += 3, tmp -= res;ny += tmp / 10 * 3 + y % 5;res = 10 - tmp % 10;y = ny;}printf("%lld\n", ans);return 0;
}❥完结撒花~ 希望下个赛季能拿到奖牌吧~
❥也祝愿小伙伴们能拿到自己想要的成绩！
