|
比赛链接
C
输入三角形的一条边，输出另外两条可以和他组成一个直角三角形的整数边。
以前似乎做过，但是忘记了可以 的公式，但时间范围很长可以直接递归
公式：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<set>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<deque>
#define go(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define ll long long
#define MOD 1000000007
#define N 100005
using namespace std;
ll y,z;
void work(ll x){
if(x==4){
y=3;
z=5;
}
else if (x%2){
y=(x*x)/2;
z=(x*x)/2+1;
}
else{
work(x/2);
y*=2;
z*=2;
}
return;
}
int main(){
ll x;
scanf("%lld",&x);
if (x==1||x==2) printf("-1");
else {
work(x);
printf("%lld %lld",y,z);
}
}
D
BITSET的一些妙用
刚开始想用线段树强解，发现dfs更新很麻烦，在网上看了一下大家的代码，用bitset就很方便了，因为只有0/1的状态，
用树状结构存储往回跳的步骤，最后dfs搜索即可，ans即时更新。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<set>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<deque>
#include<bitset>
#define go(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define ll long long
#define MOD 1000000007
#define N 100005
using namespace std;
bitset<1005>b[1005];
bitset<1005>c;
int n,m,Q,p[N],tot=0,head[N];
struct edge{
int v, next;
}e[N*2];
struct op{
int x,i,j;
}q[N];
void addedge(int u, int v){
e[++tot]=(edge){v,head[u]};
head[u]=tot;
}
void dfs(int now, int ans){
if (now==Q+1) return;
if (q[now].x==1){
int tmp=b[q[now].i][q[now].j];
if (!tmp) b[q[now].i][q[now].j]=1, ans++;
p[now]=ans;
for (int i=head[now];i;i=e[i].next){
dfs(e[i].v,ans);
}
if (!tmp) b[q[now].i].reset(q[now].j),ans--;
}
else if (q[now].x==2){
int tmp=b[q[now].i][q[now].j];
if (tmp) b[q[now].i][q[now].j]=0, ans--;
p[now]=ans;
for (int i=head[now];i;i=e[i].next){
dfs(e[i].v,ans);
}
if (tmp) b[q[now].i][q[now].j]=1,ans++;
}
else if (q[now].x==3){
int cnt=b[q[now].i].count();
b[q[now].i]^=c;
ans=ans-cnt+(m-cnt);
p[now]=ans;
for (int i=head[now];i;i=e[i].next){
dfs(e[i].v,ans);
}
b[q[now].i]^=c;
ans=ans-(m-cnt)+cnt;
}
else if (q[now].x==4){
p[now]=ans;
for (int i=head[now];i;i=e[i].next){
dfs(e[i].v,ans);
}
}
}
int main(){
int k;
scanf("%d%d%d",&n,&m,&Q);
go(i,1,m) c[i]=1;
q[0].x=4;
go(i,1,Q){
scanf("%d",&q[i].x);
if (q[i].x==1||q[i].x==2)scanf("%d%d",&q[i].i,&q[i].j);
else if (q[i].x==3) scanf("%d",&q[i].i);
if (q[i].x==4){
scanf("%d",&k);
addedge(k,i);
}
else addedge(i-1,i);
}
dfs(0,0);
go(i,1,Q){
printf("%d\n",p[i]);
}
}
E
比赛的时候并没有思路，感觉二维线段树肯定会超时，然后滚去上课。
然后查题解发现并不会，然后看到一个题解是用主席树写的，（于是学习了一下主席树，创新性的给自己写了一个非递归模板，这题根本用不了，只好重新写了一个递归的）。
题目的思路主要是：
1.先把每个garland的点都读进一个vector保存，sort成以x为第一关键字的顺序序列
2.离线处理询问，将询问按顺序读入，对于每个询问，记录当前garland开关的状态（处理方式是记录每个garland会对哪些询问做出贡献，而非直接记录状态）
3.利用主席树对于每个garland（的y）建立主席树，然后利用主席树的结构限制x的范围，达到二维的目的（666）
以及has[i].size()出现了一些bug，size的形式是unsigned int，-1之后就是无穷大了，注意。
关于vector的size的一些讲解
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<set>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<deque>
#define N 2005
#define ll long long
#define go(i,a,b) for (ll i=a;i<=b;i++)
using namespace std;
struct place{
int x,y;
ll w;
bool operator< (const place b){
if (x==b.x) return y<b.y;
return x<b.x;
}
};
struct node{
int ls,rs;
ll sum;
}t[N*20];
struct query{
int x1,y1,x2,y2,typ,i;
}q[1000005];
int top[N];
bool now[N];
vector<place>gar[N];
vector<int>has[N];
char s[20];
ll cnt,ans[1000005];
int updata(int pre, int l, int r, int pos, int c){
ll rt=++cnt;
t[rt]=t[pre];
t[rt].sum+=c;
if (l==r) return rt;
int m=(l+r)/2;
if (pos<=m) t[rt].ls=updata(t[pre].ls,l,m,pos,c);
else t[rt].rs=updata(t[pre].rs,m+1,r,pos,c);
return rt;
}
ll query(int rt1, int rt2, int l, int r, int left, int right){
if (l>right||r<left) return 0;
if (left<=l&&r<=right){
return t[rt2].sum-t[rt1].sum;
}
int m=(l+r)/2;
return query(t[rt1].ls,t[rt2].ls,l,m,left,right)+
query(t[rt1].rs,t[rt2].rs,m+1,r,left,right);
}
int main(){
int n,m,k,len,x,y,Q;
ll w;
while (scanf("%d%d%d",&n,&m,&k)!=EOF){
go(i,1,k){
now[i]=true;
scanf("%d",&len);
go(j,1,len){
scanf("%d%d%lld",&x,&y,&w);
gar[i].push_back((place){x,y,w});
}
sort(gar[i].begin(),gar[i].end());
}
scanf("%d",&Q);
go(i,1,Q){
scanf("%s",s);
if (s[0]=='S'){
scanf("%d",&q[i].i);
q[i].typ=1;
now[q[i].i]^=1;
}
else{
//cout<<"!"<<endl;
scanf("%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2);
q[i].typ=2;
go(j,1,k){
if (now[j]) has[j].push_back(i);
}
}
}
go(i,1,k){
cnt=0;
go(j,0,gar[i].size()-1){
top[j+1]=updata(top[j],1,m,gar[i][j].y,gar[i][j].w);
}
//cout<<i<<endl;
for (int j=0;j<=has[i].size()-1;j++){
if (has[i].size()==0) break;
int tmp=has[i][j];
int x1=q[tmp].x1,y1=q[tmp].y1,x2=q[tmp].x2,y2=q[tmp].y2;
place temp=(place){x2,m+1};
int pos=lower_bound(gar[i].begin(),gar[i].end(),temp)-gar[i].begin();
if (pos) ans[tmp]+=query(0,top[pos],1,m,y1,y2);
temp=(place){x1,0};
pos=lower_bound(gar[i].begin(),gar[i].end(),temp)-gar[i].begin();
if (pos) ans[tmp]-=query(0,top[pos],1,m,y1,y2);
}
}
go(i,1,Q){
if (q[i].typ==2) printf("%lld\n",ans[i]);
}
}
return 0;
}
|
转播
