A
前缀和优化
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
//#define mod 1000000009
//#define mod 1000000007
ll a[100005];
ll dp[105][105];
ll ta[105];
ll qz[100005];
ll pfqz[100005];
int main()
{
ll t, n, l, r, k;
ll summ;
cin >> t;
for(int o=1; o<=t; o++)
{
cin >> n;
for (int i=1; i<=n; i++)
{
cin >> a[i];
}
qz[0]=0;
for(int i=1;i<=n;i++)
{
qz[i]=qz[i-1] + a[i];
}
pfqz[0]=0;
for(ll i=1; i<=n; i++)
{
pfqz[i]=pfqz[i-1] + i * i;
}
cin >> qq;
for(int o=1; o<=qq; o++)
{
cin >> l;
cin >> r;
cin >> k;
if((r-l)==0)
{
printf("%lld\n", k * k + a[l]);
continue;
}
summ=qz[r] - qz[l-1];
summ += pfqz[r-l+1] - pfqz[r-l+1-k];
printf("%lld\n", summ);
}
}
return 0;
}
B
出题人出这种题疑似家庭有点幸福了
C
由样例可知，该题是要求卡特兰数。但是题目中说明两个附庸结构不是完全不同的当且仅当可以通过交换任意次任意城邦主的左右附庸结构后得到完全相同的附庸结构，所以只能求一半的卡特兰数。同时特判 和
相等的情况，预处理后
查询即可。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
//#define mod 1000000009
//#define mod 1000000007
ll dp[1004];
int main()
{
int t;
dp[1]=dp[2]=1;
cin>>t;
for(int i=3;i<=1000;i++)
{
for(int j=1;j<=(i-1)/2;j++)
{
if(j!=i-j-1)
dp[i]+=dp[j]*dp[i-1-j];
else
{
dp[i]+=dp[j]*(dp[j]+1)/2;
}
dp[i]%=998244353;
}
dp[i]+=dp[i-1];
dp[i]%=998244353;
}
while(t--)
{
int n;
cin>>n;
int i;
cout<<dp[n]<<endl;
}
return 0;
}
F
倒着找 串，直到下一个串出现前记录答案。
#include <bits/stdc++.h>
int res[200005];
using namespace std;
int main()
{
int n;
string s;
s.clear();
cin>>s;
int dp[100];
n = s.length();
for(int i = 1; i <= 50; i++)
{
dp[i] = 0;
}
s = '0' + s;
for(int i = n; i >= 1; i--)
{
if(s[i]=='l')
{
if(dp[2] > i)
{
dp[1] = dp[2];
}
}
else if(s[i]=='e')
{
dp[8] = i;
if(dp[3] > i)
{
dp[2] = dp[3];
}
if(dp[4] > i)
{
dp[3] = dp[4];
}
}
else if(s[i]=='t')
{
if(dp[5] > i)
{
dp[4] = dp[5];
}
}
else if(s[i]=='c')
{
if(dp[6] > i)
{
dp[5] = dp[6];
}
}
else if(s[i]=='o')
{
if(dp[7] > i)
{
dp[6] = dp[7];
}
}
else if(s[i]=='d')
{
if(dp[8] > i)
{
dp[7] = dp[8];
}
}
res[i] = dp[1];
}
for(int i = 1; i <= n; i++){
printf("%d ", res[i]);
}
printf("\n");
return 0;
}
G
签到
print("1000000000000000000000000000057")
H
排序后根据题意暴力枚举即可。需要特判当前时间没有任务处于等待中的状态。记录 最大值和位置进行更新。
趣事：用 输出
类型的数会使用科学计数法，因为这个罚了五发。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
//#define mod 1000000009
//#define mod 1000000007
struct pro
{
double b,co;
int id;
bool operator<(pro a)
{
if(a.b!=b)
{
return b<a.b;
}
else return id<a.id;
}
}a[5005];
bool flag[5005];
double ans[5005];
int main()
{
int n;
cin>>n;
int i;
for(i=1;i<=n;i++)
{
cin>>a[i].b>>a[i].co;
a[i].id=i;
}
sort(a+1,a+1+n);
double t=a[1].co+a[1].b;
flag[a[1].id]=1;
ans[a[1].id]=a[1].b;
int j;
double best;
int bestloc;
for(i=2;i<=n;i++)
{
best=-1145141919;
double minn=LINF;
int minloc;
for(j=1;j<=n;j++)
{
if(flag[a[j].id]) continue;
if(a[j].b>t)
{
if(minn>a[j].b)
{
minn=a[j].b;
minloc=j;
}
else if(minn==a[j].b)
{
if(a[minloc].id>a[j].id)
{
minloc=j;
}
}
continue;
}
if(best<1.0+(t-a[j].b)/a[j].co)
{
best=1.0+(t-a[j].b)/a[j].co;
bestloc=j;
}
else if(best==1.0+(t-a[j].b)/a[j].co)
{
if(a[bestloc].b>a[j].b)
{
bestloc=j;
continue;
}
if(a[bestloc].b==a[j].b)
{
if(a[bestloc].id>a[j].id)
{
bestloc=j;
continue;
}
}
}
}
if(best==-1145141919)
{
t=minn+a[minloc].co;
flag[a[minloc].id]=1;
ans[a[minloc].id]=t-a[minloc].co;
continue;
}
flag[a[bestloc].id]=1;
ans[a[bestloc].id]=t;
t+=a[bestloc].co;
}
for(i=1;i<=n;i++) printf("%.0lf\n",ans[i] );
return 0;
}
I
签到
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
//#define mod 1000000009
//#define mod 1000000007
int q[200005];
int mp[1005][1005];
int main()
{
int n, x, qq, op, a, b;
ll summ;
char c;
cin >> n;
for(int i=0; i <= n + 1; i++)
{
for(int j=0; j <= n + 1; j++)
{
mp[i][j]=0;
}
}
cin >> qq;
for(int o=1; o <= qq; o++)
{
cin >> op;
if(op==1){
cin >> a;
cin >> c;
b=c - 'a';
//cin >> b;
for(int j=1; j <= n; j++)
{
mp[a][j]=b;
}
}
else if(op==2)
{
cin >> a;
cin >> c;
b=c - 'a';
//cin >> b;
for(int i=1; i <= n; i++)
{
mp[i][a]=b;
}
}
else if(op==3)
{
cin >> a;
cin >> c;
b=c - 'a';
//cin >> b;
for(int i=1; i <= n; i++)
{
int j=a - i;
if((j<1)||(j>n))
{
continue;
}
mp[i][j]=b;
}
}
else if(op==4)
{
cin >> a;
cin >> c;
b=c - 'a';
//cin >> b;
for(int i=1; i <= n; i++)
{
int j=i - a;
if((j<1)||(j>n))
{
continue;
}
mp[i][j]=b;
}
}
else
{
cin >> x;
for(int j=1; j <= n; j++)
{
printf("%c", mp[x][j] +'a');
}
printf("\n");
}
}
return 0;
}
J
预处理每对点之间的距离并用map维护，再用向量点乘的性质判断夹角是否是钝角。
玄学复杂度，看起来是 的但没超时。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
//#define mod 1000000009
//#define mod 1000000007
struct point
{
double x,y;
}a[1005];
bool yes(double x,double y)
{
if(fabs(x-y)<1e-7) return 0;
else return 1;
}
int main()
{
int n;
map<double,vector<int> > mp[1005]; //记录每个点到其他点的距离以及下标
cin>>n;
int i,j;
for(i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j) continue;
double l=hypot(a[i].x-a[j].x,a[i].y-a[j].y);
mp[i][l].push_back(j);
}
}
ll cnt=0;
int t,s;
for(i=1;i<=n;i++)
{
for(auto[j,k]:mp[i])
{
if(k.size()<=1) continue;
for(t=0;t<k.size();t++)
{
for(s=t+1;s<k.size();s++)
{
double x1=a[k[t]].x-a[i].x,x2=a[k[s]].x-a[i].x;
double y1=a[k[t]].y-a[i].y,y2=a[k[s]].y-a[i].y;
double ji=x1*x2+y1*y2;
double len1=sqrt(x1*x1+y1*y1);
double len2=sqrt(x2*x2+y2*y2);
if(ji<0&&yes(-1.0,ji/(len1*len2)))
{
cnt++;
}
}
}
}
}
cout<<cnt<<endl;
return 0;
}
K
比较明显的 。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
//#define mod 1000000009
#define mod 1000000007
ll dp[5000][5000];
ll n,m;
int main()
{
cin>>n>>m;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1;
dp[i][j]%=mod;
}
cout<<dp[n][m]<<endl;
return 0;
}
L
签到
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n, temp;
long long summ=0;
string s;
s.clear();
cin>>s;
temp = 0;
summ = 0;
for(int i = 0; i < s.length(); i++)
{
if(s[i]=='0')
{
temp = 0;
summ -= 12;
}
else
{
temp++;
if(temp>=2&&temp<=6)
{
summ += temp-1;
summ += 3;
}
else if(temp>6)
{
summ += 5;
summ += 3;
}
else
{
summ+=3;
}
}
}
printf("%lld\n", summ);
return 0;
}
京公网安备 11010502036488号