第528场肯定是要去做一做的
就按照GCD那样子搞一搞，中间答案累加一下就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
ll Ans;
void Solve(ll a,ll b){
if (b==0) return;
Ans+=a/b;
Solve(b,a%b);
}
int main(){
Solve(IN(),IN());
OUT(Ans);
}
我是把每对字符的出现位置都存了一下，
然后先找有没有 $(i,j)和(j,i) (i\ne j)$ 都出现过的，
有就直接交换，输出 $Cnt-2$
否则就找一下有没有 $(i,j)和(j,k) (i\ne j\ne k)$，
有的话也换一下，输出 $Cnt-1$
否则直接输出 $Cnt$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=200005;
int n;
char S[N],T[N];
int Ps[30][30];
int main(){
n=IN();
scanf("%s%s",S+1,T+1);
int Ans=0;
Rep(i,1,n){
Ps[S[i]-'a'][T[i]-'a']=i;
if (S[i]!=T[i]) Ans++;
}
Rep(i,0,25) Rep(j,i+1,25){
if (Ps[i][j]&&Ps[j][i]){
printf("%d\n%d %d\n",Ans-2,Ps[i][j],Ps[j][i]);
return 0;
}
}
Rep(i,0,25) Rep(j,0,25){
if (i==j||!Ps[i][j]) continue;
Rep(k,0,25){
if (j==k||!Ps[j][k]) continue;
printf("%d\n%d %d\n",Ans-1,Ps[i][j],Ps[j][k]);
return 0;
}
}
printf("%d\n",Ans);
puts("-1 -1");
}
这题可以把行和列分开来考虑
然后以行为例
我用了两个set，一个记录修改，一个记录每段的长度
然后修改的时候我们把它的前驱和后缀都拎出来，
就能知道切的这一段长度是多少
然后把这一段拎出来切断再放进去
再把这次修改放到管修改的那个set里
输出的时候输出行最大值和列最大值的乘积就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
multiset<int>Hor,Ver,Mdh,Mdv;
int w,h,n,x;
char opt[2];
int main(){
w=IN(),h=IN(),n=IN();
Hor.insert(h),Ver.insert(w);
Mdh.insert(1),Mdh.insert(h+1);
Mdv.insert(1),Mdv.insert(w+1);
Rep(i,1,n){
scanf("%s",opt);
x=IN()+1;
if (opt[0]=='H'){
multiset<int>::iterator it=Mdh.lower_bound(x);
int Mx=*it,Mn=*--it,L=Mx-Mn;
Mdh.insert(x);
Hor.erase(Hor.find(L));
Hor.insert(x-Mn),Hor.insert(Mx-x);
OUT(1ll*(*--Hor.end())*(*--Ver.end())),putchar('\n');
}
else{
multiset<int>::iterator it=Mdv.lower_bound(x);
int Mx=*it,Mn=*--it,L=Mx-Mn;
Mdv.insert(x);
Ver.erase(Ver.find(L));
Ver.insert(x-Mn),Ver.insert(Mx-x);
OUT(1ll*(*--Hor.end())*(*--Ver.end())),putchar('\n');
}
}
}
两个点之间连点的条件是它们之间的距离大于它们的权值之和
很容易想到把一个点看成一条线段，
然后题意就变成了选尽量多的线段并使它们不相交
排序以后随便搞一搞就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=200005;
struct Seg{
int l,r;
bool operator <(const Seg&x)const{return l<x.l;}
}a[N];
int n,Ls[N<<1],Lc,Ks,F[N<<1];
map<int,int>Li;
int main(){
n=IN();
Rep(i,1,n){
int x=IN(),w=IN();
a[i].l=x-w;a[i].r=x+w;
Ls[++Lc]=a[i].l,Ls[++Lc]=a[i].r;
}
sort(Ls+1,Ls+Lc+1);
Li[Ls[1]]=++Ks;
Rep(i,2,Lc) if (Ls[i]!=Ls[i-1]) Li[Ls[i]]=++Ks;
Rep(i,1,n){a[i].l=Li[a[i].l];a[i].r=Li[a[i].r];}
sort(a+1,a+n+1);
int Ans=0,Nw=1;
Rep(i,1,Ks){
Ans=max(Ans,F[i]);
while (Nw<=n&&a[Nw].l==i){
F[a[Nw].r]=max(F[a[Nw].r],Ans+1);
Nw++;
}
}
OUT(Ans);
}
题意就是让所有的点出度和入度都是偶数
首先不管方向，把度数为奇数的点之间随便连一下边
然后跑欧拉回路，如果边数是偶数，那就这么连：
$A->B<-C->D<-E...<-A$
如果是奇数的话，先给 $A$ 连个自环，后面都一样
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=100005,M=200005;
int to[M*2+N],next[M*2+N],head[N],vis[M*2+N],cnt;
void AddEdge(int u,int v){
to[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
}
int n,m,Lt[N],As[M<<2][2],Ans,Eu[M*2+N],v;
void DFS(int u){
for (int &i=head[u];~i;){
if (vis[i]){i=next[i];continue;}
int v=to[i];
vis[i]=vis[i^1]=1;
i=next[i];
DFS(v);
}
Eu[++v]=u;
}
int main(){
n=IN(),m=IN();
memset(head,-1,sizeof head);
Rep(i,1,m){
int u=IN(),v=IN();
AddEdge(u,v);AddEdge(v,u);
Lt[u]++,Lt[v]++;
}
int Lst=0;
Rep(i,1,n) if (Lt[i]&1){
if (!Lst) Lst=i;
else AddEdge(Lst,i),AddEdge(i,Lst),Lst=0;
}
Ans=0;
Rep(u,1,n){
Cross(i,u){
if (vis[i]) continue;
v=0;
DFS(u);
if (!(v&1)){
As[++Ans][0]=Eu[1];
As[Ans][1]=Eu[1];
}
Rep(j,1,v-1){
if (j&1) As[++Ans][0]=Eu[j],As[Ans][1]=Eu[j+1];
else As[++Ans][0]=Eu[j+1],As[Ans][1]=Eu[j];
}
}
}
OUT(Ans),putchar('\n');
Rep(i,1,Ans){
OUT(As[i][0]),putchar(' '),OUT(As[i][1]),putchar('\n');
}
}
标算好像是FFT hhh
然而可以用 Bitset 使过去
把 $A.T.G.C$ 分开考虑，
然后就可以搞成01的形式
随便搞一下就好了 不懂可以留言
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=200005;
int n,m,k,Nw,Tmp[N];
char S[N],P[N];
bitset<N>Ex[4],Ans;
int main(){
n=IN(),m=IN(),k=IN();
scanf("%s%s",S,P);
Rep(i,0,n-1){
if (S[i]=='A') S[i]=0;if (S[i]=='T') S[i]=1;
if (S[i]=='G') S[i]=2;if (S[i]=='C') S[i]=3;
}
Rep(i,0,m-1){
if (P[i]=='A') P[i]=0;if (P[i]=='T') P[i]=1;
if (P[i]=='G') P[i]=2;if (P[i]=='C') P[i]=3;
}
Rep(Lt,0,3){
memset(Tmp,0,sizeof Tmp);
Rep(i,0,n-1) if (S[i]==Lt) Tmp[max(0,i-k)]++,Tmp[min(n,i+k+1)]--;
Nw=0;Rep(i,0,n-1) Nw+=Tmp[i],Ex[Lt][i]=Nw?1:0;
}
Rep(i,0,n-m) Ans[i]=1;
Rep(i,0,m-1) Ans&=Ex[P[i]]>>i;
int Cnt=0;
Rep(i,0,n-m) Cnt+=(int)Ans[i];
OUT(Cnt);
}
官方题解是$n^2logn$
然后民间一大堆 $n^2$ 的
我随便找了一个看了一下
简单来说就是，三角形ABC的面积等于：
$\frac{A\times B+B\times C+C\times A}{2} (\times 是叉积)$
然后就考虑每两个交点连成的边对于答案的贡献
是两个点的叉积乘以$\frac{1}{2*总三角形个数}$
为什么分母要乘二呢？因为三角形面积要除二233
但是直接算的话是$n^3$的
然后就考虑一条直线上所有的交点的贡献
因为 $A\times B+A\times C=A\times (B+C)$
所以前缀和搞一下就可以了
然而因为算叉积的时候，
要么所有三角形都顺时针算，要么都逆时针
所以为了防止乱算，我们把所有直线按斜率排序
大家可以自己手画一下，这样能保证都是同一方向
然后枚举直线之后，
按顺序把它其它直线与它的交点顺序加进去，
算一下贡献， 再加到前缀和里面
好了 其实我知道你们都没有看懂0.0
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=3005;
struct Point{
double a,b,c,ang;
bool operator <(const Point&x)const{return ang>x.ang;}
}p[N];
PDD Intersec(Point a,Point b){
double Tmp=b.a*a.b-a.a*b.b;
double x=(b.c*a.b-a.c*b.b)/Tmp;
double y=(a.c*b.a-b.c*a.a)/Tmp;
return mk(x,y);
}
double cross(PDD a,PDD b){
return a.fr*b.sc-a.sc*b.fr;
}
int n;
int main(){
n=IN();
Rep(i,1,n){
p[i].a=IN(),p[i].b=IN(),p[i].c=IN();
if (p[i].a>0) p[i].a=-p[i].a,p[i].b=-p[i].b,p[i].c=-p[i].c;
}
Rep(i,1,n) p[i].ang=atan2(-p[i].a,p[i].b);
sort(p+1,p+n+1);
double Ans=0,Pb=3.0/n/(n-1)/(n-2);
Rep(i,1,n){
PDD Pre=mk(0,0);
Rep(j,1,n-1){
int k=(i+j-1)%n+1;
PDD Cur=Intersec(p[i],p[k]);
Ans+=Pb*cross(Cur,Pre);
Pre.fr+=Cur.fr,Pre.sc+=Cur.sc;
}
}
printf("%.10lf\n",Ans);
}
Aug 22, 2022 12:53:29 PM
We advise any test-takers who wish to review their Assam intermediate Question Paper 2023 to do so. visit the official website to obtain the Assam Board 11th Class Question Paper 2023 from the primary online page of the Assam Higher Secondary Education Council. All candidates who show up for the exam are only entitled to get their sample paper. Assam +1 Question Paper 2023 In order to check their Assam Board 11th class Important Question Paper 2023 and learn more about this board, we advise students to visit the official website. On this website, we offer tips and information on how students may prepare for exams. Important Question Paper for SEBA +1 in 2023. simply go to the directions to obtain your 2023 11th Class Important Question Paper.
Apr 16, 2023 06:38:19 PM
In certain cases your mail may be exposed to public that Modelpapers works on giving out better service in different forms and we do not sell or giveaway your personal information other than public info giving out by you. We are very conscious about mail spam model-paper.com and we try to protect every email as much as possible.