首页 > 代码库 > SRM 587 DIV1

SRM 587 DIV1

2024-07-07 23:10:22   222人阅读

550

结论：同一层的交点共线。

很容易猜到，也可以跑几组数据验证。

利用结论就可以按层算，再利用对称性简化计算。

 1 using namespace std;
 2 #define maxn 70100
 3 class TriangleXor {
 4 public:
 5     int theArea(int);
 6 };
 7 double l[maxn] , x[maxn] , y[maxn] , H;
 8 int idx;
 9 
10 void addpoint(double k,double w) {// y = kx + 1 , y = x/w
11     double X = w/(1.0-k*w);
12     double Y = X/w;
13     x[++idx] = X;
14     y[idx] =Y;
15 }
16 
17 double dist(double x0,double y0,double x1,double y1) {
18     return sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));
19 }
20 
21 int TriangleXor::theArea(int w) {
22     double ans = 0.0;
23     if (w%2==0) {
24         ans = 0.5 * w / 2.0;
25     }
26     x[0] = y[0] = 0;
27     for (int i=1 ; i<=w ; i++ ) {
28         addpoint(-1.0/(double)i,w);
29     }
30     // H = (double)w / sqrt(1.0+w*w);
31     for (int i=0 ; i<w ; i+=2 ) {
32         if (i+1<=w) {
33             // double tmp = dist(x[i],y[i],x[i+1],y[i+1]);
34             // ans += tmp*H;
35             H = x[i+1]-x[i];
36             ans += H;
37         }
38     }
39     for (int i=0 ; i<w ; i+=2 ) if (i+2<=w) {
40         H = y[i+2] - y[i];
41         double len = 2.0 * (0.5-y[i+1]) * (double)w;
42 //        double len = w-2*x[i+1];
43         ans += len * H / 2.0;
44     }
45     cout<<ans<<endl;
46     return (int)floor(ans);
47 }
View Code

 

 900

结论：用01串表示"NZ",任意两行（两列）要么相等，要么取反。

利用结论，贪心地在每一位枚举并检验，枚举复杂度O(n^2) ,检验复杂度O(n^3),总复杂度O(n^5)。

检验方法： g[i][j]表示第i,j行是否相同,利用cells求出部分i,用类似传递闭包的办法递推所有能求出来的关系，同时检验是否会有矛盾。

 1 class ThreeColorability {
 2 public:
 3     vector <string> lexSmallest(vector <string>);
 4 };
 5 #define maxn 55
 6 int g[maxn][maxn],n,m;
 7 
 8 int check(vector<string> c) {
 9     memset(g,-1,sizeof(g));
10     for (int i=0; i<n; i++ ) {
11         g[i][i] = 0;
12         for (int j=i+1; j<n; j++ ) {
13             for (int k=0; k<m; k++ ) if (c[i][k]!=‘?‘ && c[j][k]!=‘?‘) {
14                 if (g[i][j]==-1) {
15                     g[i][j] = (c[i][k]!=c[j][k]);
16                     g[j][i] = g[i][j];
17                 } else {
18                     if (g[i][j] && c[i][k]==c[j][k]) return 0;
19                     if (!g[i][j] && c[i][k]!=c[j][k]) return 0;
20                 }
21             }
22         }
23     }
24     for (int i=0; i<n; i++ )
25     for (int j=0; j<n; j++ )
26     for (int k=0; k<n; k++ )
27     if (g[j][i]!=-1 && g[i][k]!=-1) {
28         if (g[j][k]==-1) g[j][k] = g[j][i]^g[i][k];
29         else if (g[j][k] != (g[j][i]^g[i][k])) return 0;
30     }
31     return 1;
32 }
33 
34 vector <string> ThreeColorability::lexSmallest(vector <string> c) {
35     n = c.size();
36     m = c[0].size();
37     memset(g,-1,sizeof(g));
38     
39     if (!check(c)) return {};
40     
41     for (int i=0; i<n; i++ ) for (int j=0; j<m; j++ ) if (c[i][j]==‘?‘) {
42         c[i][j]=‘N‘;
43         if (!check(c)) c[i][j] = ‘Z‘;
44     }
45     return c;
46 }
View Code

 

 


联系
我们