A.字元串顯示數字a+b problem(5.16)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
char c[30][10][10];
char p[30][10][10];
int cnt,num,x[3],ret[100];
int judge(int m){
int counter=0;
for(int i=1;i<=7;i++)
for(int j=1;j<=5;j++)
if(c[m][i][j]=='x') counter++;
if(counter==9) return -1;
if(counter==7) return 1;
if(counter==20) return 0;
if(counter==14) return 4;
if(counter==11) return 7;
if(counter==23) return 8;
if(counter==21&&c[m][2][5]=='x') return 9;
if(counter==21) return 6;
if(counter==19&&c[m][6][1]=='x') return 2;
if(counter==19&&c[m][2][5]=='x') return 3;
if(counter==19) return 5;
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
strcpy(p[1][1],"....x");
strcpy(p[1][2],"....x");
strcpy(p[1][3],"....x");
strcpy(p[1][4],"....x");
strcpy(p[1][5],"....x");
strcpy(p[1][6],"....x");
strcpy(p[1][7],"....x");
strcpy(p[2][1],"xxxxx");
strcpy(p[2][2],"....x");
strcpy(p[2][3],"....x");
strcpy(p[2][4],"xxxxx");
strcpy(p[2][5],"x....");
strcpy(p[2][6],"x....");
strcpy(p[2][7],"xxxxx");
strcpy(p[3][1],"xxxxx");
strcpy(p[3][2],"....x");
strcpy(p[3][3],"....x");
strcpy(p[3][4],"xxxxx");
strcpy(p[3][5],"....x");
strcpy(p[3][6],"....x");
strcpy(p[3][7],"xxxxx");
strcpy(p[4][1],"x...x");
strcpy(p[4][2],"x...x");
strcpy(p[4][3],"x...x");
strcpy(p[4][4],"xxxxx");
strcpy(p[4][5],"....x");
strcpy(p[4][6],"....x");
strcpy(p[4][7],"....x");
strcpy(p[5][1],"xxxxx");
strcpy(p[5][2],"x....");
strcpy(p[5][3],"x....");
strcpy(p[5][4],"xxxxx");
strcpy(p[5][5],"....x");
strcpy(p[5][6],"....x");
strcpy(p[5][7],"xxxxx");
strcpy(p[6][1],"xxxxx");
strcpy(p[6][2],"x....");
strcpy(p[6][3],"x....");
strcpy(p[6][4],"xxxxx");
strcpy(p[6][5],"x...x");
strcpy(p[6][6],"x...x");
strcpy(p[6][7],"xxxxx");
strcpy(p[7][1],"xxxxx");
strcpy(p[7][2],"....x");
strcpy(p[7][3],"....x");
strcpy(p[7][4],"....x");
strcpy(p[7][5],"....x");
strcpy(p[7][6],"....x");
strcpy(p[7][7],"....x");
strcpy(p[8][1],"xxxxx");
strcpy(p[8][2],"x...x");
strcpy(p[8][3],"x...x");
strcpy(p[8][4],"xxxxx");
strcpy(p[8][5],"x...x");
strcpy(p[8][6],"x...x");
strcpy(p[8][7],"xxxxx");
strcpy(p[9][1],"xxxxx");
strcpy(p[9][2],"x...x");
strcpy(p[9][3],"x...x");
strcpy(p[9][4],"xxxxx");
strcpy(p[9][5],"....x");
strcpy(p[9][6],"....x");
strcpy(p[9][7],"xxxxx");
strcpy(p[0][1],"xxxxx");
strcpy(p[0][2],"x...x");
strcpy(p[0][3],"x...x");
strcpy(p[0][4],"x...x");
strcpy(p[0][5],"x...x");
strcpy(p[0][6],"x...x");
strcpy(p[0][7],"xxxxx");
for(int i=1;i<=7;i++){
char ch;
cnt=1;num=0;
while((ch=getchar())!='\n'&&ch!=EOF){
if(cnt!=1&&num==0) ch=getchar();
num++;
c[cnt][i][num]=ch;
if(num==5) num=0,cnt++;
}
}
int d=1;
for(int i=1;i<cnt;i++){
if(judge(i)==-1) d=2;
else x[d]=x[d]*10+judge(i);
}
int ans=x[1]+x[2];
cnt=0;
for(;ans;ans=ans/10) ret[++cnt]=ans%10;
for(int i=1;i<=7;i++){
for(int j=cnt;j>=1;j--){
for(int k=0;k<5;k++)
printf("%c",p[ret[j]][i][k]);
if(j!=1) printf(".");
}
printf("\n");
}
return 0;
}
B.
C.
D.給定n,求最小長度的連續數字和=n。n<=10^9(5.16)
設l+(l+1)+…+r=n
(l+r)*(r-l+1)/2=n
(l+r)*(r-l+1)=2*n
l+r,r-l+1一奇一偶,暴力?
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
int T,t,a,b,ans,ansl,ansr;
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--){
ans=;
scanf("%d",&t);t*=;a=;b=t;
while(!(b&)) b/=,a*=;
if(a<b) {
ans=a;
ansl=(b-a+)/;
ansr=(b+a-)/;
}else{
ans=b;
ansl=(a-b+)/;
ansr=(b+a-)/;
}
if(ans==) ans=inf;
for(int i=;i<=(int)sqrt(t);i++)
if(b%i==) {
if(ans<i) break;
else {
ans=i;
a=i;b=t/a;
ansl=(b-a+)/;
ansr=(b+a-)/;
}
}
if(ans!=inf) {
printf("%d = ",t/);
for(int i=ansl;i<ansr;i++) printf("%d + ",i);printf("%d\n",ansr);
}
else printf("IMOPOSSIBLE\n");
}
return ;
}
E.齒輪相切可逆向轉動,已知1号輪子的轉速為1,順時針,求其他輪子的轉動情況。(n<=1000)(5.16)
相鄰輪子連邊,周遊。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 1005
#define M 1000005
using namespace std;
struct A {int x,y,r;}a[N];
struct E {int to,nxt;}edge[M*];
int T,n;
int dis[N],idx[N],tot;
queue<int>q;
double dist(int x1,int y1,int x2,int y2){
return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
bool judge(int i,int j){
return dist(a[i].x,a[i].y,a[j].x,a[j].y)==(double)(a[i].r+a[j].r);
}
void addedge(int from,int to){
// printf("%d %d\n",from,to);
edge[tot].to=to;edge[tot].nxt=idx[from];idx[from]=tot++;
}
void bfs(){
q.push();dis[]=;
while(!q.empty()){
int x=q.front();q.pop();
for(int t=idx[x];t;t=edge[t].nxt){
E e=edge[t];
if(!dis[e.to]){
dis[e.to]=dis[x]+;
q.push(e.to);
}
}
}
}
int gcd(int a,int b){
return b==?a:gcd(b,a%b);
}
void getans(int x,int y){
int d=gcd(x,y);
x=x/d;y=y/d;
if(y==) printf("%d ",x);
else printf("%d/%d ",x,y);
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--){
tot=;
memset(a,,sizeof(A));
memset(edge,,sizeof(E));
memset(idx,,sizeof(idx));
memset(dis,,sizeof(dis));
scanf("%d",&n);
for(int i=;i<=n;i++){
int x,y,r;
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);
for(int j=;j<i;j++)
if(judge(i,j)) addedge(i,j),addedge(j,i);
}
bfs();
for(int i=;i<=n;i++){
if(dis[i]) getans(a[].r,a[i].r);
if(!dis[i]) printf("not moving\n");
else if(dis[i]&) printf("clockwise\n");
else printf("counterclockwise\n");
}
}
return ;
}
F.求平面内矩形面積并。(n<=100)(5.17)
按照橫坐标離散化。考慮從下至上掃描每條邊,cnt[i]記錄第i條水準線段覆寫情況。掃描矩形下邊界對應橫坐标(已離散化)+1,矩形上邊界對應橫坐标-1。每掃描完一個,統計新增面積。+1/-1可以線段樹維護。但n<=100。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
struct S{
double l,r,h;
int f;
bool operator < (const S &t)const{
return h<t.h;
}
}ss[N*];//水準線段掃描線
struct seg{
int l,r,cnt;
double len;
}t[N**];
int n,m,num,tot;
double ans;
double pos[N*];
void getlen(int k){
if(t[k].cnt) t[k].len=pos[t[k].r+]-pos[t[k].l];
else if(t[k].l==t[k].r) t[k].len=;
else t[k].len=t[k<<].len+t[k<<|].len;
}
int binary(double x,int l,int r){
while(l<r){
int mid=(l+r)/;
if(pos[mid]<x) l=mid+;
else r=mid;
}
return l;
}
void build(int k,int l,int r){
t[k].l=l;t[k].r=r;t[k].len=;t[k].cnt=;
if(l==r) return;
int mid=(r+l)/;
build(k<<,l,mid);build(k<<|,mid+,r);
}
void upd(int k,int a,int b,int val){
if(k>*N) return;
int l=t[k].l,r=t[k].r;
if(b<l||r<a) return;
if(a<=l&&r<=b) {
t[k].cnt+=val;
getlen(k);
return;
}
upd(k<<,a,b,val);upd(k<<|,a,b,val);
getlen(k);
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(scanf("%d",&n)&&n!=){
num=;ans=;m=;tot++;
memset(ss,,sizeof(S));
memset(t,,sizeof(seg));
memset(pos,,sizeof(pos));
for(int i=;i<=n;i++){
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
num++;ss[num].l=x1;ss[num].r=x2;ss[num].h=y1;ss[num].f=;//下邊
num++;ss[num].l=x1;ss[num].r=x2;ss[num].h=y2;ss[num].f=-;//上邊
pos[num-]=x1;pos[num]=x2;
}
sort(ss+,ss++num);
sort(pos,pos++num);//離散化
pos[]=-;
for(int i=;i<=num;i++) if(pos[i]!=pos[i-]) pos[++m]=pos[i];//去重 線段樹[1,m]
build(,,m);
for(int i=;i<=num;i++){//掃描線
int l=binary(ss[i].l,,m+);
int r=binary(ss[i].r,,m+)-;
upd(,l,r,ss[i].f);
ans+=(ss[i+].h-ss[i].h)*t[].len;
//printf("%.2lf\n",ans);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",tot,ans);
}
return ;
}