A - 9x9 (abc389 A)

题目大意

给定形如9x9的三位输入，把这个式子结果算出来

解题思路

scanf

代码

void solve()
{
    int a, b;
    scanf("%dx%d", &a, &b);
    cout << a * b;
}

B - tcaF (abc389 B)

题目大意

给定X，保证X=n!，求n

解题思路

循环即可

代码

#define ll long long
void solve()
{
    ll n;
    cin >> n;
    ll x = 1;
    int i = 1;
    while (x < n) {
        if (x * i == n) cout << i;
        x *= i;
        i++;
    }
}

C - Snake Queue (abc389 C)

题目大意

有好多条蛇排队，一开始队列是空的，一共有Q次查询。

第一种给定l，将长度为l的蛇添加到队列末尾，如果队列是空的，那么蛇头位置是0，否则是前面所有蛇长度之和。

第二种表示最前面的蛇离开队列，剩下所有的蛇头位置会减去这条蛇的长度。

第三种给定k，问此时队列从前向后第k条蛇的蛇头位置。

解题思路

模拟一下，想咋做都行，我的方法是开一个vector记录当前每条蛇的蛇头位置，如果有蛇入队，就把新的蛇长加上加进队列，并且我在一开始压入一个0。

具体效果：比如三条蛇长度为2，3，4入队，那么v：0，2，5，9

第一条蛇蛇头位置为0，第二条为2，第三条为5，最后那个9其实暂时不表示蛇头位置，只是蛇长总和，有新蛇进来他就自动变成新蛇的蛇头位置了。

弹出的话就在vector里记录一个d表示有几条蛇出去了就行，查询第k条，那么其实查询的是第k+d条，然后减去前d条的蛇长即可。

代码

#define ll long long
#define pb push_back

void solve()
{
    int T;
    cin >> T;
    vector<ll> v;
    v.pb(0);
    int d = 0;
    while (T--) {
        int c, x;
        cin >> c;
        if (c == 1) {
            cin >> x;
            v.pb(*v.rbegin() + x);
        }
        else if (c == 2) {
            d++;
        }
        else {
            cin >> x;
            cout << v[x + d - 1] - v[d] << endl;
        }
    }
}

D - Squares in Circle (abc389 D)

题目大意

有一个由1*1方格组成的无限大的网格，问以一个方格的中心作为圆心，R作为半径的圆中，完整包括了多少个方格。

解题思路

数据范围1e6，做法也很多，可以利用单调性，我是枚举高度然后勾股定理。

代码

void solve()
{
    double n;
    cin >> n;
    ll ans = 0;
    for (double i = 1.5;i <= n;i += 1.0) {
        double h = i;
        double c = sqrt(1.0 * n * n - h * h);
        if (c > 0.5) ans += floor(c - 0.5) * 2 + 1;
    }
    ans *= 2;
    double h = 0.5;
    double c = sqrt(1.0 * n * n - h * h) * 2.0;
    ans += floor(c);
    cout << ans << endl;
}

E - Square Price (abc389 E)

题目大意

有无限多的物品，第i种物品的价格为pi，如果第i种物品买了k个，那么需要花费$k^2p_i$的钱

现在有M块，问最多买多少件物品

解题思路

对于$k^2p_i$的条件我们可以拆开看，第一件是pi元，那么第二件就是3pi元，第三件是5pi，因为项数为k的1,3,5,7等差数列之和就是k^2，我们可以看做每件商品买了之后会涨价。

那么我们的策略肯定是哪个便宜买哪个，从最便宜的开始买起，我们需要知道买到一件多少钱的商品时总价要超过M了，那么这是一个很显然的二分，二分这件最贵的商品的价格，然后我们要算总价，总价我们可以根据每一种商品的单价推出这种商品买了多少个，从而可以算出总价，总价要小于M。

二分出的价格为mid，某个商品价格为pi，如果这个商品买了x件，那么有(x*2-1)pi<=mid，也就可以除一下算出x，那么总价就是pix^2。

那么这里还有一个问题，有可能很多件商品的最贵的价格相同，比如3种商品价格分别为3，5，7。那么对于105，他们三都有可能价格为105，105也就可以买1~3件，那么我们算出不买这件最贵商品剩下多少钱，最后再除一下加上这种最贵商品即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,p[200005];long long m;
bool check(long long mid){
	long long sum=0;
	for(int i=1;i<=n;i++){
		long long tmp=(mid+p[i])/(2ll*p[i]);
		if(tmp>INT_MAX)return false;
		if(tmp*tmp>(long long)INT_MAX*INT_MAX/p[i])return false;
		sum+=tmp*tmp*p[i];
		if(sum>=m)return false;
	}
	return true;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>p[i];
	long long l=1,r=1e18;
	while(l<=r){
		long long mid=l+r>>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		long long tmp=((l-1)+p[i])/(2ll*p[i]);
		ans+=tmp;
		m-=tmp*tmp*p[i];
	}
	cout<<ans+m/l<<endl;
	
}