百川网站,网站营销培训,填手机号码的广告,WordPress完整安裝包题目#xff1a; 任意门
听说这套题目是叉姐出的#xff0c;感觉呵呵了。。。 据说现场牌都不够发的#xff01;#xff01;#xff01;只能说给湖南省出的题目太强了#xff0c;不适合新手去做#xff0c;当然我这种老手也不见得做的多好#xff0c;出了3题#xf…题目 任意门
听说这套题目是叉姐出的感觉呵呵了。。。 据说现场牌都不够发的只能说给湖南省出的题目太强了不适合新手去做当然我这种老手也不见得做的多好出了3题赶在了三等首但是感觉自己被碾压惨了尤其看到出题人的解释时。。。 Problem A: 2016
题意
中文题目给定nm求a*b%201601an, 1bm) 的数的对数。
思路
第一眼看到这破题的时候首先想到了容斥不过看了一下榜2分钟都有人出貌似有简单的做法但是这明显是一个数论的题目有毛毛的简单做法。
容斥原理不怎么确定也没敢急着敲索性先打下表然而悲催的是并没什么规律然后继续推算了写一发容斥先看看对不对胡搞一番已经接近一个小时了有点捉急但是写出来连样例都不过调调改改一直不对也没心思看剩下的题接近两个小时就有点不想做了正是困的时候而且现在还是爆零的状态一下也没提交前面有了划分第一个数余数然后求第二个数的余数的想法但是在枚举第二个数的时候老是剪不好。
2个小时多一点的时候试验室中都还在改TLE的代码我突然想起来直接2016*2016的算法直接枚举两个数的余数无非在不同的剩余系里这两个数的余数相乘如果是2016的倍数那么原数一定也是就这么搞过去了当然有可优化的余地当时脑袋都懵了开了数组。
code
#include bits/stdc.h
using namespace std;typedef long long ll;ll v1[2018],v2[2018];ll n,m,s;
void sol(){ll pn/2016,qm/2016,ppn%2016,qqm%2016;for (ll i0;i2016;i) v1[i]p;for (ll i0;i2016;i) v2[i]q;for (ll i1;ipp;i) v1[i];for (ll i1;iqq;i) v2[i];v1[2016]v1[0];v2[2016]v2[0];for (ll i1;i2016;i){for (ll j1;j2016;j){if (i*j%20160) sv1[i]*v2[j];}}coutsendl;
}
int main()
{while (~scanf(%lld%lld,n,m)){s0;sol();}
}
Problem G: Parenthesis
题意
给定一个括号串每次交换两个位置问交换后是否合法。
思路
这道是队友看的也是一开始就过去的开始我的想法是把看作是1看作是-1然后修改也就是维护前缀和可用线段树或树状数组。不过后来看队友的做法是贪心的做法只要是左边的那个是就一定能成功。然后Onq的做法实际上因为贪心掉一大部分远远达不到大概也直到On。
code
#includebits/stdc.h
using namespace std;
const int maxn1e55;
char s[maxn];
int x[maxn],y[maxn],n,q;bool solve(int a,int b){if(s[a]s[b])return true;if(s[a]))return true;bool ok1;for(int ia;ib;i)if(x[i]y[i]1)ok0;return ok;
}int main(){while(~scanf(%d%d,n,q)){scanf(%s,s1);x[0]y[0]0;for(int i1;in;i){x[i]x[i-1];y[i]y[i-1];if(s[i]()x[i];else y[i];}int a,b;while(q--){scanf(%d%d,a,b);if(ab)swap(a,b);if(solve(a,b))puts(Yes);else puts(No);}}return 0;
}
Problem J: 三角形和矩形
题意 中文题目给定一个三角形和一个矩形求交的面积。
思路
几何不怎么搞但这肯定是套版题目不过后来听说硬算分情况也可以因为之前见过HDU 3060求两个多边形并的题目拿过来直接用了稍加修改就过了。
code
#includestdio.h
#includestring.h
#includestdlib.h
#includemath.h
#includealgorithm
const int maxn 555;
const int maxisn 10;
const double eps 1e-8;
const double pi acos(-1.0);
int dcmp(double x)
{if(x eps) return 1;return x -eps ? -1 : 0;
}
inline double min(double a, double b)
{return a b ? a : b;}
inline double max(double a, double b)
{return a b ? a : b;}
inline double Sqr(double x)
{return x * x;}
struct Point
{double x, y;Point(){x y 0;}Point(double a, double b){x a, y b;}inline Point operator-(const Point b)const{return Point(x - b.x, y - b.y);}inline Point operator(const Point b)const{return Point(x b.x, y b.y);}inline double dot(const Point b)const{return x * b.x y * b.y;}inline double cross(const Point b, const Point c)const{return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);}inline double len(){return sqrt(dot(*this));}
};
Point LineCross(const Point a, const Point b, const Point c, const Point d)
{double u a.cross(b, c), v b.cross(a, d);return Point((c.x * v d.x * u) / (u v), (c.y * v d.y * u) / (u v));
}
double PolygonArea(Point p[], int n)
{if(n 3) return 0.0;double s p[0].y * (p[n - 1].x - p[1].x);p[n] p[0];for(int i 1; i n; i)s p[i].y * (p[i - 1].x - p[i 1].x);return fabs(s * 0.5);
}
double CPIA(Point a[], Point b[], int na, int nb)
{Point p[maxisn], tmp[maxisn];int i, j, tn, sflag, eflag;a[na] a[0], b[nb] b[0];memcpy(p, b, sizeof(Point) * (nb 1));for(i 0; i na nb 2; i){sflag dcmp(a[i].cross(a[i 1], p[0]));for(j tn 0; j nb; j, sflag eflag){if(sflag 0) tmp[tn ] p[j];eflag dcmp(a[i].cross(a[i 1], p[j 1]));if((sflag ^ eflag) -2)tmp[tn ] LineCross(a[i], a[i 1], p[j], p[j 1]);}memcpy(p, tmp, sizeof(Point) * tn);nb tn, p[nb] p[0];}if(nb 3) return 0.0;return PolygonArea(p, nb);
}
double SPIA(Point a[], Point b[], int na, int nb)
{int i, j;Point t1[4], t2[4];double res 0, if_clock_t1, if_clock_t2;a[na] t1[0] a[0], b[nb] t2[0] b[0];for(i 2; i na; i){t1[1] a[i - 1], t1[2] a[i];if_clock_t1 dcmp(t1[0].cross(t1[1], t1[2]));if(if_clock_t1 0) std::swap(t1[1], t1[2]);for(j 2; j nb; j){t2[1] b[j - 1], t2[2] b[j];if_clock_t2 dcmp(t2[0].cross(t2[1], t2[2]));if(if_clock_t2 0) std::swap(t2[1], t2[2]);res CPIA(t1, t2, 3, 3) * if_clock_t1 * if_clock_t2;}}return PolygonArea(a, na) PolygonArea(b, nb) - res;
}Point p1[8], p2[8];
double x[8],y[8];
double san(){double l1fabs(y[1]-y[2]);double l2fabs(x[1]-x[2]);return l1*l2*0.5;
}
double si(){double hhfabs(y[4]-y[3]);double wwfabs(x[4]-x[3]);return ww*hh;
}
int n1, n2;
int main()
{int i;while(~scanf(%lf%lf%lf%lf,x[1],y[1],x[2],y[2])){n13;n24;scanf(%lf%lf%lf%lf,x[3],y[3],x[4],y[4]);p1[2].set(x[1],y[1]);p1[1].set(x[1],y[2]);p1[0].set(x[2],y[1]);p2[3].set(x[3],y[3]);p2[2].set(x[3],y[4]);p2[1].set(x[4],y[4]);p2[0].set(x[4],y[3]);double sssan()si();printf(%.9f\n, fabs(ss-SPIA(p1, p2, n1, n2)));}return 0;
}
