总结：
这次还是状态不佳，只出了一道题。队内一直看一道题，导致效率不太高，下次改变做题策略。
我要评论给你n和p，然后给n个数字，然后可以让两个相邻数字合并，问你任意次操作后最多能有多少个数字%p==0。
一开始想着dp，然后写了一下发现不会。就想着暴力来做，先求每两个给定的数字%p==0之间的前缀和，然后做差类似尺举。
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int a[100005]={0};
int b[100005]={0};
int main()
{
int t;int n,p;
scn(t);
//init();
while(t--){
scn(n);scn(p);
ll ans=0;
for(int i=1;i<=n;i++){
scn(a[i]);
a[i]%=p;
b[i]=b[i-1]+a[i];
}
int head=0;
for(int i=1;i<=n;i++){
if(a[i]==0) {
ans++;head=i;
//cout<<ans<<" "<<b[i]<<" !!! "<<i<<endl;
}
else{
for(int j=head;j<i;j++){
//cout<<head<<" "<<b[i]<<" "<<b[j]<<endl;
if((b[i]-b[j])%p==0) {
//cout<<ans<<" "<<b[i]<<" "<<b[j]<<endl;
ans++;
head=i;
break;
}
}
}
}
printf("%lld\n",ans);
}
return 0;
}
图中有一个极小的球被封闭在一个边长为L的等边三角形中。球的半径为1e-1000，可以被看作是一个点。
为了清楚的表达球的位置，我们我们基于这个三角形建立了一个平面坐标系。原点位于三角形底边的中点，X轴沿底边（从左到右），Y轴沿底边的高度（从下至上）。例如，三角形的顶点位于（-L/2，0），（0，3^(1/2)L/2），（L/2，0）。
一开始，球在水平方向的速度是vx每秒钟，垂直方向是vy每秒钟。换句话说，球的初始速度是(vx2+vy2)^(1/2)每秒，方向向量为（vx,vy）。
如果球现在在这个位置（x，y），t秒后，它将移动到该位置（x+t，y+t)，在此过程中没有接触到边界。
当球碰到边界的任何边缘时，会发生完全弹性的碰撞，这意味着球的运动方向会根据反射定律而改变，但其速度不会改变。
反射定律遵循入射角等于反射角的规律。如上图所示，入射角等于反射角β。
现在考虑到这个三角形的边长L，开始时，球的位置（x，y）以及它的速度vx,vy)，你能计算多长时间发生k次碰撞了吗？
在k次碰撞以内，保证球在三角形内不会碰到任何顶点。
但是在第一回k次碰撞之后，球可能会碰到三角形的任何顶点，例如，在第三个例子。
球不接触三角形的任何顶点的说法意味着从球到三角形最近两条边的距离不同时等于球的半径。
有多组数据。给出L，x，y，vx，vy，k。对于所有的测试用例，都保证球在开始时严格地在三角形内部，并且如上所述，在第一回k次碰撞内，在三角形内，球不会接触到三角形的任何顶点。
对于所有测试用例，也保证球的速度大于0。
输出第k次碰撞发生时的时间。
标注三角形顶点，A（0，3^(1/2)L/2），B（L/2，0），C（-L/2，0）。作A关于BC垂线AO，以BC为x轴，AO为y轴建立平面直角坐标系。
由反射定律和球的运动规律得，将三角形以碰撞边为轴进行翻折，球在第一次和第二次碰撞之间的轨迹与初始位置到第一次碰撞之间的轨迹在一条直线上，且第三次及之后的碰撞的轨迹也在这条直线上。
所以，小球的碰撞次数为转化后的运动轨迹穿过的三角形边的条数。记为小球运动轨迹在y轴上的分量dy，三角形的高位h=L*3^(1/2）/2，其中计算水平的三角形边数为dy/h。
余下两条斜的直线的计算，将坐标系按顺时针旋转120°、逆时针旋转120°可求得。
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false),cin.tie(0);
#define ll long long
#define inf 0x3f3f3f3f
const int N=1e5+5;
//set<string>b;
//set<string>::iterator it;
const double eps=1e-8;
const double pi=acos(-1.0);
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
else if(x>0) return 1;
return -1;
}
struct Point
{
double x,y;
Point(){}
Point(double a,double b)
{
x=a;
y=b;
}
Point operator -(const Point &b)const
{
return Point(x-b.x,y-b.y);
}
double operator ^(const Point &b)const
{
return x*b.y-y*b.x;
}
double distance(Point p)
{
return hypot(x-p.x,y-p.y);
}
Point Rotate(double rad)
{
return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));
}
};
struct Line
{
Point s,e;
Line(){}
Line(Point a,Point b)
{
s=a;
e=b;
}
double getDis(Point a)
{
return fabs((a-s)^(e-s))/s.distance(e);
}
};
double L,x,y,vx,vy,h;
Point A,B,C,S,v1,v2,v3;
Line AB,AC,BC;
ll k;
void init()
{
h=L*sqrt(3.0)/2.0;
v1=Point(vx,vy);
v2=v1.Rotate(2.0*pi/3);
v3=v1.Rotate(-2.0*pi/3);
S=Point(x,y);
A=Point(0,h);
B=Point(L/2.0,0);
C=Point(-L/2.0,0);
AB=Line(A,B);
AC=Line(A,C);
BC=Line(B,C);
}
ll Num(double dy)
{
ll ans=0;
if(dy>=0) ans+=(ll)(dy/h);
else ans+=(ll)(-dy/h)+1;
return ans;
}
bool judge(double t)
{
ll ans=0;
double dy;
dy=BC.getDis(S)+v1.y*t;
ans+=Num(dy);
dy=AC.getDis(S)+v2.y*t;
ans+=Num(dy);
dy=AB.getDis(S)+v3.y*t;
ans+=Num(dy);
return ans>=k;
}
int main()
{
IO;
int T;
double l,r,mid;
cin>>T;
while(T--)
{
cin>>L>>x>>y>>vx>>vy>>k;
init();
l=0.0;r=1e10;
while((r-l)>=1e-4)
{
mid=(r+l)/2.0;
if(judge(mid)) r=mid;
else l=mid;
}
cout<<fixed<<setprecision(10)<<mid<<endl;
}
return 0;
}
按题目会给出一个字符串，呢么我们先将给出的字符串进行匹配，最终剩下没有匹配的字符串，除去’*‘号，最左边的可能就是’)’，最右边的可能就是’(’，为什么说可能，因为可能一边没有，但是也没有匹配。
首先左右括号不可能区间相交，所以我们只需要记录每个括号的左边或者右边 * 号数量是否够即可，然后对于)取最早出现的 ，取完为止，若号的数量少于未匹配的一种括号数量显然是不匹配的，我们只需要对两种括号进行检查即可，最后对原字符串赋值即可。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
const int maxn = 3e5 + 5;
map<ll, ll> mp;
int pre[maxn], vis[30];
char dp[maxn];
vector<ll> vec;
typedef pair<char, int> p;
stack<p> q;
ll a[maxn], sum[maxn];
char pc[maxn];
char s[maxn];
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
int t;
cin >> t;
while (t--)
{
while (!q.empty())
q.pop();
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; i++) //得到未匹配的字符串pc
{
pc[i] = s[i];
if (s[i] == '(')
q.push(p(s[i], i));
else if (s[i] != '*')
{
if (!q.empty())
pc[q.top().second] = pc[i] = '!', q.pop();
}
}
bool fla = false;
int lp = 0, rp = 0, k = n + 1;
for (int i = 1; i <= n; i++)//检查）的数量并查看是否可以构造出合格的括号
{
if (pc[i] == '*')
lp++;
if (pc[i] == ')')
{
if (!lp)
{
fla = true;
break;
}
rp++, lp--;
}
if (pc[i] == '(')
{
k = i;
break;
}
}
for (int i = 1; i <= n; i++)//若可以成功最早出现的*变为(,为匹配的)--
{
if (pc[i] == '*' && rp)
s[i] = '(', rp--;
}
lp = 0, rp = 0;//以上同理
for (int i = n; i >= k; i--)
{
if (pc[i] == '*')
rp++;
if (pc[i] == '(')
{
if (!rp)
{
fla = true;
break;
}
rp--, lp++;
}
}
for (int i = n; i >= k; i--)
{
if (pc[i] == '*' && lp)
s[i] = ')', lp--;
}
if (fla)
puts("No solution!");
else
{
for (int i = 1; i <= n; i++)
{
if (s[i] != '*')
putchar(s[i]);
}
puts("");
}
}
}
给出n,k，构造出一个n的全排列P，使得对于 1~n 中任意的数 i，P 都存在一个长为 i 的子区间，其和模 n 余 k。有解输出任意一组，无解输出 -1
奇偶分开讨论可以依次添加,偶数只有k=(n+1)*n/2%k 奇数只有k=0
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
scanf("%d%d",&n,&k);
int sum = n*(n+1)/2;
if(sum%n==k){
if(n%2==1){
for(int i=1; i<=(n-1)/2; ++i){
printf("%d %d ",i,n-i);
}
printf("%d\n",n);
}
else{
for(int i=1; i<=(n-2)/2; ++i){
printf("%d %d ",i,n-i);
}
printf("%d %d",n/2,n);
}
}
else
printf("-1\n");
return 0;
}
本文地址：https://blog.csdn.net/weixin_43912188/article/details/107896968
如对本文有疑问， 点击进行留言回复！！
【贪心】P1792 [国家集训队]种树 & P1484 种树
网友评论