C-Snake Queue#
题目大意#
有一个蛇队列。最初，队列是空的。
您将获得 Q个查询，应按给出的顺序进行处理。查询有三种类型：
- 类型 1 ：以
1 l的形式给出。长度为 l的蛇被添加到队列末尾。如果队列在添加之前是空的，则新添加的蛇的头部位置为 0 ；否则，它是队列中最后一条蛇的头部坐标和最后一条蛇的长度之和。 - 类型 2 ：以
2的形式给出。队列前面的蛇离开队列。保证队列此时不为空。令 mm 为离开的蛇的长度，则队列中剩余的每个蛇的头部坐标减少 m 。 - 类型 3 ：以
3 k形式给出。输出从队列前面开始第 k 条蛇的头部坐标。保证此时队列中至少有 k 条蛇
思路#
比赛时第一想法是把蛇的队列在类型二时一个一个修改仍在队列中的值，但时间复杂度过高。第二想法是记录已经出队的蛇的长度，坐标减去已经出队的蛇的长度就是当前的坐标。题目保证了让队列前面的蛇离开队列过程中保证不为空，则队列为空添加时就是第一次，无需将已经出队蛇的长度归零。即每条新进入队列的蛇的坐标保持递增！
代码#
#include <bits/stdc++.h>
using namespace std;
struct snake
{
long long h;
long long m;
};
deque<snake> snakes;
int main(){
int q;
cin>>q;
long long outs = 0;
while(q--){
int t;
cin>>t;
if(t==1)
{
long long l;
cin>>l;
if(snakes.size()){
long long x = snakes.back().h;
long long y = snakes.back().m;
snakes.push_back({x+y,l});
}
else snakes.push_back({0,l});
}
else if(t==2)
{
long long m = snakes.front().m;
outs-=m;
snakes.pop_front();
}
else if(t==3)
{
long long k;
cin>>k;
cout<<snakes[k-1].h+outs<<endl;
}
}
return 0;
}
D-Squares in Circle#
题目大意#
On the two-dimensional coordinate plane, there is an infinite tiling of 1×11×1 squares. Consider drawing a circle of radius R centered at the center of one of these squares. How many of these squares are completely contained inside the circle? More precisely, find the number of integer pairs (i,j) such that all four points (i+0.5,j+0.5)(i+0.5,j+0.5), (i+0.5,j−0.5)(i+0.5,j−0.5), (i−0.5,j+0.5)(i−0.5,j+0.5), and (i−0.5,j−0.5)(i−0.5,j−0.5) are at a distance of at most R from the origin.
思路#
考试时做出来的，但在小数上犯了大车。技巧：可以同时乘以4，让括号内的0.5变为1,避免出现小数
代码#
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll r;
cin >> r;
ll m = (r-1)*4+1;
ll n = 0;
for(ll i = 3;i<2*r;i+=2){
n+=(ll)(sqrt(4*r*r - i*i)-1)/2;
}
cout<<m+4*n<<endl;
return 0;
}
E-Square Price#
题目大意#
有 N种产品，每种产品有 件库存。 您可以购买任意非负数量的每种产品。要购买第 i个产品的 k 件，需要花费 日元。 如果您的总购买成本最多为 M日元，您总共可以购买的最大单位数是多少？
约束#
- 所有输入值均为整数。
思路#
看到M非常大，枚举时间复杂度太高，注意到每件产品的花费为 即每件产品是单调递增的，可以考虑用二分法。设每次最多买价格为X的商品。注意是能够全部买完X，则右移，如果只能买部分的X，需要左移。最后再用剩下的钱看能否再买部分的价格为X+1的商品。 特别注意溢出，数字太大，最好都开大一些
代码#
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
ll ans;
ll n,m;
const int N = 2e6+10;
vector<ll> p(N);
bool check(int x)
{
__int128 ans = 0;
for(int i = 1;i<=n;i++)
{
int temp = (x/p[i]+1)/2;
ans+=(__int128)p[i]*temp*temp;
if(ans>m) return false;
}
return true;
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
cin>>p[i];
}
int l = 0;
int r = m;
int ans= -1;
while(l <= r)
{
ll mid = (l+r)/2;
if(check(mid))
{
ans = mid;//一定可以全部购买<=mid的，更新答案
l = mid+1;
}
else r = mid-1;
}
int res = 0;
for(int i = 1;i<=n;i++)
{
int temp = (ans/p[i]+1)/2;
res+=temp;
m-=temp*temp*p[i];
}
res+=m/(ans+1);
cout<<res<<endl;
return 0;
}F-Rated Range#
题目大意#
Takahashi 计划参加 N场 AtCoder 比赛。
在第 i 场比赛( 1≤i≤N)中，如果他的评分在 Li和 Ri之间(含)，他的评分将增加 1。
您将获得以下格式的 Q个查询：
- 给出一个整数 X 。假设 Takahashi 的初始评分为 X ，请在参加所有 N 场比赛后确定他的评分。
思路#
后续重做