DUT Star Round2

A.Zeratu的军训游戏

Problems: 开灯问题，问无数次操作之后第n盏灯的状态

Analysis:

　　cj:平方数有奇数个约数

Tags: Implementation

B.Zeratud的完美区间

Problems: 给定一个1..n的全排列，询问区间[l, r]中的数字是否排序后连续

Analysis:

　　cj:智障的我想了一个及其错误的算法，后来被lucky_ji点醒，if (区间最大值最小值之差 == 区间长度)就好了。。

　　 Return:燃鹅楼上STILL犯了一个有趣的错误，Max-Min+1==Length，当然，区间Max和Min的维护用线段树或者倍增DP就行了

Tags: Data Structure, Dynamic Programming

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 //#include<iostream>

 #include<cmath>

 #include<queue>

 #include<map>

 #include<string>

 #include<vector>

 using namespace std;

 #define INF 2000000000

 #define Clear(x, Num) memset(x, Num, sizeof(x))

 #define Dig(x) ((x>='0') && (x<='9'))

 #define Neg(x) (x=='-')

 #define G_c() getchar()

 #define Maxn 100010

 typedef long long ll;

 int n, a[Maxn], D_min[Maxn][], D_max[Maxn][], m, l, r;

 inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }

 inline void read(int &x){ char ch; int N=; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-; while ((ch=G_c()) && (!Dig(ch))); } x=ch-; while ((ch=G_c()) && (Dig(ch))) x=x*+ch-; x*=N; }

 //inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

 void rmq_Min()

 {

     int temp=(int)(log((double)n)/log(2.0));

     for(int i=;i<n;i++) D_min[i][]=a[i];

     for(int j=;j<=temp;j++)

         for(int i=;i<n;i++)

             if(i+(<<j)<=n) D_min[i][j]=min(D_min[i][j-], D_min[i+(<<(j-))][j-]);

 }

 void rmq_Max()

 {

     int temp=(int)(log((double)n)/log(2.0));

     for(int i=;i<n;i++) D_max[i][]=a[i];

     for(int j=;j<=temp;j++)

         for(int i=;i<n;i++)

             if(i+(<<j)<=n) D_max[i][j]=max(D_max[i][j-], D_max[i+(<<(j-))][j-]);

 }

 int Minimum(int L, int H)

 {

     int k=(int)(log((double)H-L+)/log(2.0));

     return min(D_min[L][k],D_min[H-(<<k)+][k]);

 }

 int Maximum(int L, int H)

 {

     int k=(int)(log((double)H-L+)/log(2.0));

     return max(D_max[L][k],D_max[H-(<<k)+][k]);

 }

 int main()

 {

     read(n);

     for (int i=; i<n; i++) read(a[i]);

     rmq_Min(); rmq_Max();

     read(m);

     for (int i=; i<=m; i++)

     {

         read(l); read(r); l--; r--;

         int Res=Maximum(l, r)-Minimum(l, r)+;

         if (Res==r-l+) puts("YES"); else puts("NO");

     }

 }

Code By Return

C. ACM群日常禁言一万年

Problems: 秒数转换为xdays, hh/mm/ss

Analysis:

　　 Return:模拟，注意输出格式即可

Tags: Implementation

D.Zeratud与LCM

Problems: 构造长度为n的序列{a}，使得LCM(a1, a2, ......, an) = a1 + a2 + ...... + an

Analysis:

　　Return:首先想到找规律，发现n为奇数时每次在后面加上2*6^k, 3*6^k即可，然后在找n为偶数规律的时候发现，易得下列式子

　　　　　　 ∑(a_i)=Lcm(a_i) <=> 6*∑(a_i)=6*Lcm(a_i) <=> ∑(a_i*6)=6*Lcm(a_i) <=> 1+2+3+∑(a_i*6)(a_i≠1)=6*Lcm(a_i)

　　　　　　从而发现递推通式，然而，本题坑点在于对a_i的限制，然后发现只有在n=20的时候会Max{a_i}>Limit，从而进一步寻找规律可过

Tags: Math

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 //#include<iostream>

 #include<cmath>

 #include<queue>

 #include<map>

 #include<string>

 #include<vector>

 using namespace std;

 #define INF 2000000000

 #define Clear(x, Num) memset(x, Num, sizeof(x))

 #define Dig(x) ((x>='0') && (x<='9'))

 #define Neg(x) (x=='-')

 #define G_c() getchar()

 #define Maxn 10010

 typedef long long ll;

 int n, Cnt;

 ll S[Maxn];

 inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }

 inline void read(int &x){ char ch; int N=; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-; while ((ch=G_c()) && (!Dig(ch))); } x=ch-; while ((ch=G_c()) && (Dig(ch))) x=x*+ch-; x*=N; }

 //inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

 int main()

 {

     while (scanf("%d", &n)!=EOF)

     {

         if (n==) { puts("3 2 1"); continue; }

         S[]=, S[]=, S[]=, S[]=; Cnt=;

         while (Cnt<n)

         {

             for (int i=; i<=Cnt; i++) if ((S[i]!=) && (S[i]!=)) S[i]*=;

             S[++Cnt]=;

         }

         for (int i=; i<=n; i++) printf("%lld ", S[i]); puts("");

     }

 }

Code By Return

E.小q与面试题

Problems: 维护一个可以查询最小值的栈

Analysis:

　　cj: 这种题最适合用STL乱搞了

Tags: Data Structure

 #define PRON "e"

 #include <set>

 #include <stack>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 stack<int> q;

 multiset<int> s;

 char ch;

 inline void read(int & x){

     int flag = ;

     do {

         if (ch == '-')

             flag = -;

         ch = getchar();

     } while (!('' <= ch && ch <= ''));

     x = ;

     do {

         x = x *  + ch - '';

         ch = getchar();

     } while ('' <= ch && ch <= '');

     x *= flag;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen(PRON ".in", "r", stdin);

 #endif

     s.clear();

     while (not q.empty())

         q.pop();

     int T, a, b, sum = ;

     read(T);

     while (T --){

         read(a);

         if (a == ){

             read(b);

             ++ sum;

             s.insert(b);

             q.push(b);

         }

         if (a == ){

             if (sum == )

                 puts("ERROR!");

             else

                 printf("%d\n", q.top());

         }

         if (a == ){

             if (sum == )

                 puts("ERROR!");

             else

                 printf("%d\n", *s.begin());

         }

         if (a == ){

             if (sum == )

                 puts("ERROR!");

             else {

                 -- sum;

                 s.erase(s.find(q.top()));

                 q.pop();

             }

         }

     }

 }

Code by cj

F.Zeratu与QQ堂

Problems: 给定一张n*n的地图，并有m次操作，每次操作为放置炸弹（在砖块上放置视为无效操作），炸弹可以炸掉上下左右最近的砖块，输出最后剩余的砖块数

Analysis:

　　cj: 直接模拟会Time Limit Exceeded，用row[i]存储第i行的砖块的j坐标，col[j]存储第j行砖块的i坐标。每一次放置炸弹成功后，二分找到前后和左右的砖块并且erase

Tags: Implementation

 #define PRON "f"

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 #define lb lower_bound

 #define r(y, x) lb(row[y].begin(), row[y].end(), x)

 #define c(x, y)    lb(col[x].begin(), col[x].end(), y)

 const int maxn =  + ;

 int n, sum = ;

 char s[maxn][maxn];

 vector<int> row[maxn], col[maxn];

 int main(){

 #ifndef ONLINE_JUDGE

     freopen(PRON ".in", "r", stdin);

 #endif

     scanf("%d", &n);

     for (int i = ; i < n; i ++){

         scanf("%s", s[i]);

         for (int j = ; j < n; j ++)

             if (s[i][j] == '*')

                 ++ sum;

     }

     for (int i = ; i < n; i ++)

         for (int j = ; j < n; j ++)

             if (s[i][j] == '*')

                 row[i].push_back(j);

     for (int j = ; j < n; j ++)

         for (int i = ; i < n; i ++)

             if (s[i][j] == '*')

                 col[j].push_back(i);

     int q, x, y, pos;

     scanf("%d", &q);

     while (q --){

         scanf("%d %d", &y, &x);

         if ((not row[y].empty() && *(r(y, x)) == x) && (not col[x].empty() && *(c(x, y)) == y))

             continue;

         if (not row[y].empty()){

             -- sum;

             if (x < *row[y].begin()){

                 col[*row[y].begin()].erase(c(*row[y].begin(), y));

                 row[y].erase(row[y].begin());

             }

             else if (x > *(row[y].end() - )){

                 col[*(row[y].end() - )].erase(c(*(row[y].end() - ), y));

                 row[y].erase(row[y].end() - );

             }

             else {

                 -- sum;

                 pos = r(y, x) - row[y].begin();

                 col[row[y][pos]].erase(c(row[y][pos], y));

                 col[row[y][pos - ]].erase(c(row[y][pos - ], y));

                 row[y].erase(pos + row[y].begin());

                 row[y].erase(pos -  + row[y].begin());

             }

         }

         if (not col[x].empty()){

             -- sum;

             if (y < *col[x].begin()){

                 row[*col[x].begin()].erase(r(*col[x].begin(), x));

                 col[x].erase(col[x].begin());

             }

             else if (y > *(col[x].end() - )){

                 row[*(col[x].end() - )].erase(r(*(col[x].end() - ), x));

                 col[x].erase(col[x].end() - );

             }

             else {

                 -- sum;

                 pos = c(x, y) - col[x].begin();

                 row[col[x][pos]].erase(r(col[x][pos], x));

                 row[col[x][pos - ]].erase(r(col[x][pos - ], x));

                 col[x].erase(pos + col[x].begin());

                 col[x].erase(pos -  + col[x].begin());

             }

         }

     }

     printf("%d\n", sum);

 }

Code by cj

G.Zeratu的最优路径

Problems: 题面描述同最基本的数字“正方形”问题

Tags: Dynamic Programming

巴特西

DUT Star Round2

最新文章

热门文章