当前位置:网站首页>Atcoder beginer contest 258 [competition record]
Atcoder beginer contest 258 [competition record]
2022-07-06 00:12:00 【Addiction ۣۖ ิ ۣۖ ิ ۣۖ ิꦿ】
The game was very difficult ,D topic INF It's too small ,wrong Several rounds , And forget to deal with unreasonable situations while inputting and operating , A state of mind breakdown , Finally, Xi mentioned points !!!
ABC
Simulation is enough , Be careful B Don't make mistakes , Don't turn !!!C Do not cross the array , own RE A few shots !!!
D Trophy
greedy , Enumerate prefixes to play 1~i individual , Finally, give it all to No i individual , Find the minimum value .
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
const int Max=5e5+5;
int main(){
ll n,x;
cin>>n>>x;
ll mina=0;ll ans=0;
ll a,b;
cin>>a>>b;
ans+=(a+b);
mina=ans+(x-1)*b;
for(ll i=1;i<n;i++){
cin>>a>>b;
ans+=(a+b);
if(x>i){
ll temp=ans+(x-i-1)*b;
mina=min(mina,temp);
}
}
cout<<mina<<endl;
}
E Packing Potatoes
Preprocess the end point that can be reached when each subscript is used as the starting point . Found the queried K The maximum is 1e12, Therefore, it cannot be accessed circularly , At this time, we need to use multiplication , Speed up query .
#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
ll w[Max];
ll sum[Max];
int n,q,x;
int ne[45][Max];
ll res[Max];
ll getsum(ll l,ll r){
ll ans=0;
bool flag=false;
if((l-1)/n!=(r-1)/n) ans=((r-1)/n-(l-1)/n-1)*(sum[n]);
else flag=true;
if(l%n==0) l=n;
else l%=n;
if(r%n==0) r=n;
else r%=n;
if(flag) return sum[r]-sum[l-1];
return ans+sum[n]-sum[l-1]+sum[r];
}
void solve(int p){
ll l=p,r=p+1000000000,_l=l;
while(l<=r){
ll mid=(l+r)/2;
if(getsum(_l,mid)>=1ll*x) r=mid-1;
else l=mid+1;
}
res[p]=l-p+1;
ne[0][p]=l+1;
while(ne[0][p]>n) ne[0][p]-=n;
}
int main(){
sc(n);sc(q);sc(x);
for(int i=1;i<=n;i++){
sl(w[i]);sum[i]=sum[i-1]+w[i];
}
for(int i=1;i<=n;i++) solve(i);
for(int j=1;j<=40;j++){
for(int i=1;i<=n;i++){
ne[j][i]=ne[j-1][ne[j-1][i]];
}
}
while(q--){
ll k;sl(k);k--;
ll ans=1;
for(int i=40;~i;i--){
if(k-(1ll<<i)>=0){
// cout<<ans<<' ';
ans=ne[i][ans];k-=(1ll<<i);
// cout<<ans<<' '<<k<<endl;
}
}
// cout<<ans<<' ';
cout<<res[ans]<<endl;
}
}
F Main Street
F Few people have passed , Because there are many special judgments on this question , If you are not careful, you will be sentenced less , Or misjudge . Here is the code of the boss !!!
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <algorithm>
#include <array>
using namespace std;
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define forab(i, a, b) for(int i=(a);i<(b);++i)
#define foreach(i, n) for (__typeof(n.begin()) i = n.begin(); i != n.end(); ++i)
#define sqr(x) ((x)*(x))
#define clr(a, b) memset(a, b, sizeof(a))
#define MP make_pair
#define PB push_back
#define SZ(a) ((int)a.size())
#define all(a) (a).begin(),(a).end()
#define inf 0x3f3f3f3f
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
const double eps = 1e-8;
int dcmp(double x) { if (x < -eps) return -1; else return x > eps;}
#define se(x) cout<<#x<<" = "<<x<<endl
#ifdef CHEN_PC
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...)
#endif
const int N = 200010;
const int mod = 1000000007; // 10^9+7
int n;
int solve() {
ll b, k, sx, sy, gx, gy;
cin >> b >> k >> sx >> sy >> gx >> gy;
ll ans = (abs(sx - gx) + abs(sy - gy)) * k;
forn (i, 4) forn (j, 4) {
ll cur = 0;
auto gao = [&] (ll x, ll y, int dir) {
if (dir == 0) {
cur += (x % b) * k;
x = x / b * b;
}
if (dir == 1) {
cur += (b - x % b) * k;
x = x / b * b + b;
}
if (dir == 2) {
cur += (y % b) * k;
y = y / b * b;
}
if (dir == 3) {
cur += (b - y % b) * k;
y = y / b * b + b;
}
return MP(x, y);
};
auto [ux, uy] = gao(sx, sy, i);
auto [vx, vy] = gao(gx, gy, j);
cur += abs(ux - vx) + abs(uy - vy);
if (ux != vx && uy / b == vy / b) {
ll d = min(min(uy-uy/b*b, vy-vy/b*b), min(uy/b*b+b-uy, vy/b*b+b-vy));
cur += d * 2;
}
if (uy != vy && ux / b == vx / b) {
ll d = min(min(ux-ux/b*b, vx-vx/b*b), min(ux/b*b+b-ux, vx/b*b+b-vx));
cur += d * 2;
}
ans = min(ans, cur);
}
cout << ans << endl;
return 0;
}
int main(int argc, char *argv[]) {
#ifdef CHEN_PC
freopen("in.txt", "r", stdin);
#endif
while (cin >> n) {
forn (i, n)
int ret = solve();
// cout << ret << endl;
}
return 0;
}
G Triangle
enumeration 1≤i<j≤n And ai,j=1, Consider how many k Satisfy ai,k=aj,k=1 All have sides . Finding this thing is |Si∩Sj|, among Si Express satisfaction j>i,ai,j=1 Of j Set , So you can use bitset Handle .
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Max=3050;
bitset<Max>mp[Max];
char a[Max][Max];
int main(){
int n;cin>>n;
for(int i=0;i<n;i++){
scanf("%s",a[i]);
mp[i]=bitset<Max>(a[i]);
}
ll ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(a[i][j]=='1'){
ans+=(mp[i]&mp[j]).count();
}
}
}
cout<<ans/3<<endl;
}
Ex Odd Steps
Here we can compare the title to “ Go up the steps , A person from the first step , Each step can only take an odd number of steps , Finally arrive at S The possibility of , The subscript is A Don't settle on the steps of .”, At this time, we assume dp[i] To reach the steps i The possibility of , that
dp[i]=dp[i-1]+dp[i-3]+dp[i-5]...
suppose s[i] by :
s[i]=dp[i]+dp[i-2]+dp[i-4]...
so :
dp[i]=dp[i-1]+s[i-3]
And then we found out S=1e18, Circular queries are completely impossible , It can be expressed by matrix :
* =
Because it appears in A Index of the array dp[i]=0, So remember to assign some values as 0.
#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int Mod=998244353;
struct Matrix{
ll a[3][3];
friend Matrix operator *(const Matrix &a,const Matrix &b){
Matrix ans;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
ll sum=0;
for(int k=0;k<3;k++){
sum+=a.a[i][k]*b.a[k][j];
sum%=Mod;
}
ans.a[i][j]=sum;
}
}
return ans;
}
}trans;
Matrix quick_power(Matrix a,ll b){
Matrix ans;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
ans.a[i][j]=0;
}
}
ans.a[0][0]=ans.a[1][1]=ans.a[2][2]=1;
while(b){
if(b&1){
ans=ans*a;
}
b>>=1;
a=a*a;
}
return ans;
}
ll a[Max];
ll b[Max];
int main(){
int n;ll S;
sc(n);sl(S);
trans.a[0][0]=1;
trans.a[1][0]=0;
trans.a[2][0]=1;
trans.a[0][1]=1;
trans.a[1][1]=0;
trans.a[2][1]=1;
trans.a[0][2]=0;
trans.a[1][2]=1;
trans.a[2][2]=0;
Matrix ans;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
ans.a[i][j]=0;
}
}
ans.a[0][0]=1;
ll sum=0;
for(int i=1;i<=n;i++){
sl(a[i]);
ans=ans*quick_power(trans,a[i]-a[i-1]);
ans.a[0][0]=0;
}
ans=ans*quick_power(trans,S-a[n]);
cout<<ans.a[0][0]<<endl;
}
边栏推荐
- Permission problem: source bash_ profile permission denied
- Qt QPushButton详解
- Learn PWN from CTF wiki - ret2libc1
- 【GYM 102832H】【模板】Combination Lock(二分图博弈)
- Wechat applet -- wxml template syntax (with notes)
- Global and Chinese markets for pressure and temperature sensors 2022-2028: Research Report on technology, participants, trends, market size and share
- USB Interface USB protocol
- MySql——CRUD
- Yunna | what are the main operating processes of the fixed assets management system
- 【luogu CF487E】Tourists(圆方树)(树链剖分)(线段树)
猜你喜欢
What if the C disk is not enough? Let's see how I can clean up 25g of temp disk space after I haven't redone the system for 4 years?
Configuring OSPF load sharing for Huawei devices
剖面测量之提取剖面数据
Qt QPushButton详解
MySQL之函数
XML配置文件(DTD详细讲解)
MySql——CRUD
硬件及接口学习总结
How to rotate the synchronized / refreshed icon (EL icon refresh)
关于slmgr命令的那些事
随机推荐
NSSA area where OSPF is configured for Huawei equipment
Detailed explanation of APP functions of door-to-door appointment service
多普勒效应(多普勒频移)
14 MySQL view
18. (ArcGIS API for JS) ArcGIS API for JS point collection (sketchviewmodel)
第16章 OAuth2AuthorizationRequestRedirectWebFilter源码解析
The use of El cascader and the solution of error reporting
18.(arcgis api for js篇)arcgis api for js点采集(SketchViewModel)
MySQL functions
Laser slam learning record
mysql-全局锁和表锁
About the slmgr command
[designmode] composite mode
权限问题:source .bash_profile permission denied
[designmode] Decorator Pattern
Make a short video clip number of we media film and television. Where can I download the material?
PV静态创建和动态创建
微信小程序---WXML 模板语法(附带笔记文档)
【QT】Qt使用QJson生成json文件并保存
15 MySQL stored procedures and functions