Atcoder beginer contest 258 [competition record]

         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;
}