2013山东省ICPC结题报告

A、Rescue The Princess

已知一个等边三角形的两个顶点A、B，求第三个顶点C，A、B、C成逆时针方向。

常规的解题思路就是用已知的两个点列出x，y方程，但这样求出方程的解的表达式比较复杂。更为简单的方法就是以A的坐标加A、C直线的角度求解，使用atan2函数求出A、B直线的角度再加上60就是A、C的角度，使用A、B求出等边三角形的边长。

 #include <cstdio>
 #include <cmath>
 #include <iostream>

 using namespace std;

 const double pi = acos(-1.0);
 double xx1,yy1,xx2,yy2,xx3,yy3,jiao,leng;

 int main(int argc, char const *argv[])
 {
     freopen("SD_3230_Rescue_The_Princess.in","r",stdin);
     int amount;
     scanf("%d",&amount);
     while(amount--){
         scanf("%lf %lf %lf %lf",&xx1,&yy1,&xx2,&yy2);
         jiao = atan2(yy2-yy1,xx2-xx1);
         leng = sqrt(pow(xx1-xx2,)+pow(yy1-yy2,));
         xx3 = xx1 + leng*cos(jiao+pi/3.0);
         yy3 = yy1 + leng*sin(jiao+pi/3.0);
         printf("(%.2lf,%.2lf)\n", xx3,yy3);
     }
     return ;
 }

B、Thrall’s Dream

给出N个点N (0 <= N < 2001)，M条边M (0 <= M < 10001)构成的图，判断是否任意两点可达，可达输出“Kalimdor is just ahead“，否则输出”The Burning Shadow consume us all“。

首先拿到这题第一个出现脑海的想法就是一次对每个点进行dfs，并记录已经确定的结果。但是想一想肯定会TE，所以就此打住这个想法。采用targan算法求出所有的连通分量，再判断这些连通分量能否构成一条链（不能出现两个或两个以上出度为0的连通分量），能则true，否则false，关键在于使用targan算法求出所有的联通分量。targan算法：基于dfs，使用low记录该点所属连通分量，dfn记录遍历到此点的时间，如果遍历的点已经遍历过并在栈中说明出现了环，要更新的相应的low值到最小，并把小的low值回传给father，如果出现low==dfn则说明出现了一个联通分量，并且这个连通分量的所有元素一定都在栈中并且都相邻，然后将这些元素全部出栈并统计此连通分量的出度，最后如果有大于等于两个连通分量的出度为0则一定有连点不可达。

 #include <cstdio>
 #include <iostream>
 #include <cstring>
 #include <stack>

 #ifndef SYMBOL
 #define MAXN 2001
 #endif

 using namespace std;
 /*
 dfs变形的targan算法，求强连通图的强联通分量
 */

 struct node
 {
     int size;
     int indegree;
     int asked;
     int instack;
     int father;
 };

 int childs[MAXN][MAXN],low[MAXN],dfn[MAXN];
 int nodeAmount,edgeAmount,times,mins,outzero;
 stack<int> stacks;
 struct node nodes[MAXN];

 void init(){
     for (int i = ;i <= MAXN;i ++){
         nodes[i].size = ;
         nodes[i].asked = ;
         nodes[i].instack = ;
         nodes[i].indegree = ;
     }
     times = ;
     outzero = ;
     mins = ;
     memset(childs,,sizeof(childs));
     memset(low,,sizeof(low));
     memset(dfn,,sizeof(dfn));
     memset(nodes,,sizeof(nodes));
     while(!stacks.empty()){
         stacks.pop();
     }
 }

 void targan(int n){
     times ++;
     dfn[n] = times;
     low[n] = times;
     stacks.push(n);
     nodes[n].asked = ;
     nodes[n].instack = ;
     int child;
     mins = dfn[n];
     for (int i = ;i < nodes[n].size;i ++){
         child = childs[n][i];
         nodes[child].father = n;
         if (nodes[child].instack){
             mins = std::min(mins ,dfn[child]);
             mins = std::min(mins ,low[child]);
             low[n] = mins;
         }
         if (!nodes[child].asked){
             targan(child);
         }
     }
     int father = nodes[n].father;
     mins = low[father];
     mins = std::min(mins ,dfn[n]);
     mins = std::min(mins ,low[n]);
     low[father] = mins;
     if (dfn[n] == low[n]){
         int nod;
         bool isout = false;
         while(){
             nod = stacks.top();
             stacks.pop();
             nodes[nod].instack = ;
             int size = nodes[nod].size;
             int chil;
             for (int k = ;k < size;k ++){
                 chil = childs[nod][k];
                 if (low[chil] != low[nod]){
                     isout = true;
                 }
             }
             if (nod == n) break;
         }
         if (!isout){
             outzero ++;
         }
     }
 }

 bool judge(){
     if (outzero >= ){
         return false;
     }
     return true;
 }

 int main(){
     freopen("SD_3231_Thralls_Dream.in","r",stdin);
     int amount;
     scanf("%d",&amount);
     for (int i = ;i <= amount;i ++){
         scanf("%d %d",&nodeAmount,&edgeAmount);
         init();
         int from,to;
         for (int j = ;j < edgeAmount;j ++){
             scanf("%d %d",&from,&to);
             int size = nodes[from].size;
             childs[from][size++] = to;
             nodes[from].size = size;
             nodes[to].indegree ++;
         }
         for (int k = ;k <= nodeAmount;k ++){
             if (!nodes[k].asked){
                 targan(k);
             }
         }
         if (judge()) {
             printf("Case %d: Kalimdor is just ahead\n", i);
         } else {
             printf("Case %d: The Burning Shadow consume us all\n",i);
         }
     }
     return ;
 }

C、A^X mod P

f(x) = K, x = 1，f(x) = (a*f(x-1) + b)%m , x > 1，求( A^(f(1)) + A^(f(2)) + A^(f(3)) + ...... + A^(f(n)) ) modular P. 1 <= n <= 10^6，0 <= A, K, a, b <= 10^9，1 <= m, P <= 10^9

10^9无论从空间还是时间上都是不可行的，所以简单的计算绝对不行，A^(10^9)我们可以预处理一下，求A^(ki+j)直接将10^9的复杂度降了一个平方。只需求出A^k即可

 #include <cstdio>
 #include <cmath>
 #include <iostream>

 #ifndef SYMBOL
 #define MAXK 100005
 #endif

 typedef long long ll;

 using namespace std;
 /*
 合理的运用%的特性
 预处理(A^1~n)%P次方
 */

 ll n, A, K, a, b, m, P;
 ll pre1[MAXK+],pre2[MAXK+];

 void init(){
     pre1[] = pre2[] = 1LL;
     for (int i = ;i <= MAXK;i ++){
         pre1[i] = A*pre1[i-]%P;
     }
     for (int i = ;i <= MAXK;i ++){
         pre2[i] = pre2[i-]*pre1[MAXK]%P;
     }
 }

 ll gao(){
     ll res = ,t = K;
     for (int i = ;i <= n;i ++){
         res = (res + pre2[t/MAXK]*pre1[t%MAXK])%P;
         t = (a*t + b)%m;
     }
     return res;
 }

 int main(int argc, char const *argv[])
 {
     freopen("SD_3232_AX_mod_P.in","r",stdin);
     int test;
     scanf("%d",&test);
     for (int i = ;i <= test;i ++){
         scanf("%lld %lld %lld %lld %lld %lld %lld",&n,&A,&K,&a,&b,&m,&P);
         init();
         printf("Case #%d: %lld\n", i,gao());
     }
     return ;
 }

D、Rubik’s cube

求将一个两色四方格旋转致每面都是同一颜色的最小步数。

直接模拟旋转魔方进行bfs，魔方可以前后，左右，上下共有12种旋转方案，一面的向前旋转和另一面的向后旋转是同一效果，除以2剩6种旋转可能，向后旋转一下相当于向前旋转3下，除以2剩3种可能的旋转方案，再依次对三种旋转进行bfs

 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 #include <queue>
 #include <map>

 #ifndef SYMBOL
 #define CUBE 24
 #define ONLINE_JUDGE 1
 #endif

 using namespace std;

 struct node
 {
     int cu[CUBE];
     int step;
 };

 node start;
 queue<node> que;
 map<int,int> myhash;
 int rode[][] = {
     {,,,,,,,},
     {,,,},
     {,,,,,,,},
     {,,,},
     {,,,,,,,},
     {,,,}
 };

 void turn(node & n,int face){
     face<<=;
     int t = n.cu[rode[face][]];
     for (int i = ;i < ;i ++){
         n.cu[rode[face][i]] = n.cu[rode[face][i+]];
     }
     n.cu[rode[face][]] = t;
     t = n.cu[rode[face][]];
     for (int i = ;i < ;i ++){
         n.cu[rode[face][i]] = n.cu[rode[face][i+]];
     }
     n.cu[rode[face][]] = t;
     face ++;
     t = n.cu[rode[face][]];
     for (int i = ;i < ;i ++){
         n.cu[rode[face][i]] = n.cu[rode[face][i+]];
     }
     n.cu[rode[face][]] = t;
 }

 int myhashCode(const node n){
     int res = ;
     for (int i = ;i < ;i ++){
         res = n.cu[i] + (res<<);
     }
     return res;
 }

 bool isOK(const node n){
     for (int i = ;i < ;i += ){
         for (int j = ;j <= ;j ++){
             if (n.cu[i] != n.cu[i+j]){
                 return false;
             }
         }
     }
     return true;
 }

 int bfs(){
     int red = ;
     for (int i = ;i < ;i ++){
         if (start.cu[i] == ){
             red ++;
         }
     }
     if (red% != ){
         return -;
     }
     if (isOK(start)){
         return start.step;
     }
     myhash.clear();
     while(!que.empty()) que.pop();
     myhash[myhashCode(start)] = ;
     que.push(start);
     node s,t;
     while(!que.empty()){
         s = que.front();
         que.pop();
         for (int i = ;i < ;i ++){
             t = s;
             t.step ++;
             turn(t,i);
             if (myhash.find(myhashCode(t)) == myhash.end()){
                 if (isOK(t)){
                     return t.step;
                 }
                 myhash[myhashCode(t)] = ;
                 que.push(t);
             }
             turn(t,i);
             turn(t,i);
             if (myhash.find(myhashCode(t)) == myhash.end()){
                 if (isOK(t)){
                     return t.step;
                 }
                 myhash[myhashCode(t)] = ;
                 que.push(t);
             }
         }
     }
     return -;
 }

 int main(int argc, char const *argv[])
 {
     #ifndef ONLINE_JUDGE
     freopen("SD_3232_Rubiks_cube.in","r",stdin);
     #endif
     int test;
     scanf("%d",&test);
     while(test--){
         for (int i = ;i < ;i ++){
             scanf("%d",&start.cu[i]);
         }
         start.step = ;
         int res = bfs();
         if (res == -) printf("IMPOSSIBLE!\n");
         else printf("%d\n", res);
     }
     return ;
 }

E、Mountain Subsequences

在一个数字序列中求山脉序列的个数 a1 < ...< ai < ai+1 < Amax > aj > aj+1 > ... > an

找出比当前数字前面并比当前数字小的数进行dp

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #define MAX 100000
 #define MOD 2012
 using namespace std;
 //cnt记录单个字符的个数，dp记录以此字母结束的个数
 int leng,up[MAX],down[MAX],dp[],cnt[],t;
 char str[MAX];
 int main() {
     freopen("SD_3234_Mountain_Subsequences.in","r",stdin);
     while(~scanf("%d",&leng)){
         scanf("%s",str);
         memset(up,,sizeof(up));
         memset(down,,sizeof(down));
         memset(dp,,sizeof(dp));
         memset(cnt,,sizeof(cnt));
         for (int i = ;i < leng;i ++){
             t = str[i] - 'a';
             for (int j = ;j < t;j ++){
                 up[i] += dp[j] + cnt[j];
                 up[i] %= MOD;
             }
             cnt[t] ++;
             cnt[t] %= MOD;
             dp[t] += up[i];
             dp[t] %= MOD;
         }
         memset(dp,,sizeof(dp));
         memset(cnt,,sizeof(cnt));
         for (int i = leng-;i >= ;i --){
             t = str[i] - 'a';
             for (int j = ;j < t;j ++){
                 down[i] += dp[j] + cnt[j];
                 down[i] %= MOD;
             }
             cnt[t] ++;
             cnt[t] %= MOD;
             dp[t] += down[i];
             dp[t] %= MOD;
         }
         int sum = ;
         for (int i = ;i < leng-;i ++){
             sum += up[i]*down[i];
             sum %= MOD;
         }
         printf("%d\n", sum);
     }
     return ;
 }

F、Alice and Bob

(a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1)，求x^P的系数

1 <= P <= 2^0+2^1+2^2+.....+2^(n-1)，二次项有个性质2^0+2^1+......+2^(n-1)<2^n，所以可以推断出P只能由唯一的二次项系数构成。将P的二进制求出来，将其中值为1的项的系数相乘即为结果。

 #include <cstdio>
 #include <iostream>
 #include <cmath>
 #include <cstring>

 #ifndef SYMBOL
 #define MAX 55
 #endif

 using namespace std;
 /*
 定理：一个数只能由2的多项式中唯一的序列构成2^0 2^1 2^2 2^3 2^4 ,7只能由2^0 2^1 2^2构成
 */

 typedef long long ll;

 int n,dex;
 int co[MAX],binary[MAX];

 void getBinary(ll number){
     memset(binary,,sizeof(binary));
     dex = ;
     while(number){
         binary[dex++] = number%2LL;
         number /= 2LL;
     }
 }

 int calcu(ll P){
     if (P == 0LL){
         return ;//一定要考虑极限问题
     }
     ll max = ;
     for (int i = ;i < n;i ++){
         max += pow(2LL,i);
     }
     if (P > max){
         return ;//一定要考虑极限问题
     }
     getBinary(P);
     int sum = ;
     for (int i = ;i < dex;i ++){
         if (binary[i]){
             sum *= co[i];
             sum %= ;
         }
     }
     return sum;
 }

 int main(int argc, char const *argv[])
 {
     // freopen("SD_3235_Alice_and_Bob.in","r",stdin);
     // freopen("SD_3235_Alice_and_Bob.out","w",stdout);
     int test,ques;
     ll P;
     scanf("%d",&test);
     while(test--){
         scanf("%d",&n);
         for (int i = ;i < n;i ++){
             scanf("%d",&co[i]);
         }
         scanf("%d",&ques);
         while(ques--){
             scanf("%lld",&P);
             printf("%d\n",calcu(P));
         }
     }
     return ;
 }

G、A-Number and B-Number

可以被7整除或包含7的为A数字，A数字中下标为A数字的除外其余为B数字，求第n个B数字。

对位数进行dp

 #include <cstdio>
 #include <cstring>
 #include <iostream>

 #ifndef SYMBOL
 #define MAX 25
 #endif

 /*
 位数动态规划,设定最大25位,dp的方式有很多
 */
 using namespace std;

 typedef unsigned long long ull;

 ull number;
 ull dp[MAX][][];
 int bits[MAX];

 ull dfs(int d,int mod7,int have7,bool limit){
     if (!d){
         return (!mod7 || have7);
     }
     if (!limit && ~dp[d][mod7][have7]){
         return dp[d][mod7][have7];
     }
     int mn = ;
     if (limit){
         mn = bits[d];
     }
     ull sum = 0ULL;
     for (int i = ;i <= mn;i ++){
         int tmod7 = (*mod7+i)%;
         int thave7 = have7 || (i == );
         sum += dfs(d-,tmod7,thave7,(i == mn) && limit);
     }
     if (!limit){
         dp[d][mod7][have7] = sum;
     }
     return sum;
 }

 ull AAmount(ull n){
     int dex = ;
     while(n){
         bits[++dex] = n%;
         n/=;
     }
     return dfs(dex,,,true)-;
 }

 ull twoSplite(){
     ull l = 7ULL,r = (1ULL<<) - ,m;
     while(l <= r){
         m = (l+r)>>;
         ull amount = AAmount(m);
         amount = amount - AAmount(amount);
         if (amount < number){
             l = m+;
         }else {
             r = m-;
         }
         //注意这里==不能返回
     }
     return l;
 }

 int main(int argc, char const *argv[])
 {
     freopen("SD_3236_A-Number_and_B-Number.in","r",stdin);
     memset(dp,-,sizeof(dp));
     while(~scanf("%llu",&number)){
         printf("%llu\n", twoSplite());
     }
     return ;
 }

H、Boring Counting

求一定范围内一定大小范围内的数的个数。

采用线段树数据结构

 #include <cstdio>
 #include <iostream>
 #include <algorithm>

 #ifndef SYMBOL
 #define MAX 50005
 #endif

 /*无形的线段树*/
 using namespace std;

 struct num
 {
     int value;
     int dex;
     bool operator <(const num n) const {return value < n.value;};
 }nums[MAX];

 struct query
 {
     int l;
     int r;
     int a;
     int b;
     int dex;
 }querys[MAX];

 bool comp1(const query q1,const query q2) {
     return q1.a < q2.a;
 }

 bool comp2(const query q1,const query q2) {
     return q1.b < q2.b;
 }

 int nn,qn;
 int minsum[MAX<<],ans[MAX][];
 /*ans[MAX][0]记录比a小数的个数，ans[MAX][1]记录比b小数的个数，答案为ans[MAX][1]-ans[MAX][0]*/

 /*创建线段树,额外添加的问题值为在这个范围内的个数*/
 void build(int l,int r,int dex){
     if (l == r){
         minsum[dex] = ;
         return ;
     }
     int m = (l+r)>>;
     build(l,m,dex<<);
     build(m+,r,dex<<|);
     minsum[dex] = minsum[dex<<] + minsum[dex<<|];
 }

 void update(int d,int l,int r,int dex){
     if (l == r){
         minsum[dex] ++;
         return ;
     }
     int m = (l+r)>>;
     if (d <= m){
         update(d,l,m,dex<<);
     }else{
         update(d,m+,r,dex<<|);
     }
     minsum[dex] = minsum[dex<<] + minsum[dex<<|];
 }

 int queryy(int ql,int qr,int l,int r,int dex){
     if (ql <= l && qr >= r){
         return minsum[dex];
     }
     int m = (l+r)>>;
     int res = ;
     if (ql <= m){
         res += queryy(ql,qr,l,m,dex<<);
     }
     if (qr > m){
         res += queryy(ql,qr,m+,r,dex<<|);
     }
     return res;
 }

 void calculate(){
     build(,nn,);
     sort(nums+,nums+nn+);
     sort(querys+,querys+qn+,comp1);
     int dd = ;
     for (int j = ;j <= qn;j ++){
         while(dd <= nn && nums[dd].value < querys[j].a){//注意这里等于不能包括在内
             update(nums[dd].dex,,nn,);
             dd++;
         }
         ans[querys[j].dex][] = queryy(querys[j].l,querys[j].r,,nn,);
     }
     build(,nn,);
     sort(querys+,querys+qn+,comp2);
     dd = ;
     for (int j = ;j <= qn;j ++){
         while(dd <= nn && nums[dd].value <= querys[j].b){
             update(nums[dd].dex,,nn,);
             dd++;
         }
         ans[querys[j].dex][] = queryy(querys[j].l,querys[j].r,,nn,);
     }
 }

 void print(int cases){
     printf("Case #%d:\n",cases);
     for (int i = ;i <= qn;i ++){
         printf("%d\n",ans[i][]-ans[i][]);
     }
 }

 int main(int argc, char const *argv[])
 {
     freopen("SD_3237_Boring_Counting.in","r",stdin);
     int test;
     scanf("%d",&test);
     for (int i = ;i <= test;i ++){
         scanf("%d %d",&nn,&qn);
         for (int j = ;j <= nn;j ++){
             scanf("%d",&nums[j].value);
             nums[j].dex = j;
         }
         for (int j = ;j <= qn;j ++){
             scanf("%d %d %d %d",&querys[j].l,&querys[j].r,&querys[j].a,&querys[j].b);
             querys[j].dex = j;
         }
         calculate();
         print(i);
     }
     return ;
 }

I、The number of steps

递推

 #include <cstdio>
 #include <iostream>

 #define maxn 55

 using namespace std;

 double dp[maxn][maxn];

 int main()
 {
     // freopen("SD_3238_The_number_of_steps.in","r",stdin);
     int n;
     while(scanf("%d",&n),n)
     {
         double a,b,c,d,e;
         scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e);
         dp[n][]=;
         for(int i=;i<=n;++i)
             dp[n][i]=dp[n][i-]+1.0;
         for(int i=n-;i>;--i)
         {
             dp[i][]=a*dp[i+][]+b*dp[i+][]+1.0;
             for(int j=;j<n;++j)
                 dp[i][j]=c*dp[i+][j]+d*dp[i+][j+]+e*dp[i][j-]+1.0;
         }
         printf("%.2lf\n",dp[][]);
     }
     return ;
 }

J、Contest Print Server

模拟

 #include <cstdio>
 #include <iostream>

 #ifndef SYMBOL
 #define MAX 100
 #endif

 using namespace std;

 struct task
 {
     char name[];
     int page;
 }tasks[MAX];

 int n,s,x,y,mod;

 void print(){
     int task = , sum = ;
     while(task < n){
         if (sum == s){
             printf("%d pages for %s\n",,tasks[task].name);
             s=(s*x+y)%mod;
             sum = ;
         }else if (sum + tasks[task].page <= s){
             printf("%d pages for %s\n",tasks[task].page,tasks[task].name);
             sum += tasks[task].page;
             task ++;
         }else{
             printf("%d pages for %s\n",s - sum,tasks[task].name);
             sum = ;
             s=(s*x+y)%mod;
         }
     }
 }

 int main(int argc, char const *argv[])
 {
     // freopen("SD_3239_Contest Print_Server.in","r",stdin);
     // freopen("SD_3239_Contest Print_Server.out","w",stdout);
     int test;
     scanf("%d",&test);
     while(test--){
         scanf("%d %d %d %d %d",&n,&s,&x,&y,&mod);
         for (int i = ;i < n;i ++){
             scanf("%s request %d pages",tasks[i].name,&tasks[i].page);
         }
         print();
         printf("\n");
     }
     return ;
 }