2016年湖南省第十二届大学生计算机程序设计竞赛
題目： 任意門
聽說這套題目是叉姐出的，感覺呵呵了。。。
據說現場牌都不夠發的！！！只能說給湖南省出的題目太強了，不適合新手去做，當然我這種老手也不見得做的多好，出了3題，趕在了三等首，但是感覺自己被碾壓慘了，尤其看到出題人的解釋時。。。
Problem A: 2016
題意：
中文題目，給定n，m求a*b%2016==0（1<=a<=n, 1<=b<=m) 的數的對數。
思路：
第一眼看到這破題的時候，首先想到了容斥，不過看了一下榜，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 p=n/2016,q=m/2016,pp=n%2016,qq=m%2016;for (ll i=0;i<2016;i++) v1[i]=p;for (ll i=0;i<2016;i++) v2[i]=q;for (ll i=1;i<=pp;i++) v1[i]++;for (ll i=1;i<=qq;i++) v2[i]++;v1[2016]=v1[0];v2[2016]=v2[0];for (ll i=1;i<=2016;i++){for (ll j=1;j<=2016;j++){if (i*j%2016==0) s+=v1[i]*v2[j];}}cout<<s<<endl; } int main() {while (~scanf("%lld%lld",&n,&m)){s=0;sol();} }Problem G: Parenthesis
題意：
給定一個括號串，每次交換兩個位置，問交換后是否合法。
思路：
這道是隊友看的，也是一開始就過去的，開始我的想法是把（看作是+1，）看作是-1，然后修改也就是維護前綴和，可用線段樹或樹狀數組。不過后來看隊友的做法，是貪心的做法，只要是左邊的那個是）就一定能成功。然后O（nq）的做法，實際上因為貪心掉一大部分，遠遠達不到，大概也直到O（n）。
code：
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; 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 ok=1;for(int i=a;i<b;i++)if(x[i]<=y[i]+1)ok=0;return ok; }int main(){while(~scanf("%d%d",&n,&q)){scanf("%s",s+1);x[0]=y[0]=0;for(int i=1;i<=n;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(a>b)swap(a,b);if(solve(a,b))puts("Yes");else puts("No");}}return 0; }Problem J: 三角形和矩形
題意：
中文題目，給定一個三角形和一個矩形，求交的面積。
思路：
幾何不怎么搞，但這肯定是套版題目，不過后來聽說硬算分情況也可以，因為之前見過HDU 3060求兩個多邊形并的題目，拿過來直接用了，稍加修改就過了。
code：
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> 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 l1=fabs(y[1]-y[2]);double l2=fabs(x[1]-x[2]);return l1*l2*0.5; } double si(){double hh=fabs(y[4]-y[3]);double ww=fabs(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])){n1=3;n2=4;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 ss=san()+si();printf("%.9f\n", fabs(ss-SPIA(p1, p2, n1, n2)));}return 0; }總結
以上是生活随笔為你收集整理的2016年湖南省第十二届大学生计算机程序设计竞赛的全部內容，希望文章能夠幫你解決所遇到的問題。
