**原题地址：** [原题地址](http://acm.hdu.edu.cn/search.php?field=problem&key=%A1%B0%D7%D6%BD%DA%CC%F8%B6%AF-%CE%C4%D4%B6%D6%AA%D0%D0%B1%AD%A1%B1%B9%E3%B6%AB%B9%A4%D2%B5%B4%F3%D1%A7%B5%DA%CA%AE%CB%C4%BD%EC%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC&source=1&searchmode=source) **[出题人题解](https://hodam.top/myfile/acm/gdut14/solution.pdf)** **[验题人题解](https://hodam.top/myfile/acm/gdut14/solution2.pdf)** **总的来说这里的题目代码都不是那么的长，有些可能要点思维** --- ## [1001 hzy 和zsl 的生存挑战](http://acm.hdu.edu.cn/showproblem.php?pid=6461) 现在有两个人,他们被分开在了两个房间,魔王**各给他们了一个数字(可能是0或者1)** 现在要求他们两个人去猜魔王给他们的这两个数字分别是什么(或者说去猜对方拿到的数字是什么),两个人在进入房间之前是知道这件事的,但是他们在给了数字之后是**完全无法联系的**.魔王要求至少有一个人要猜对,否则他们就会 > 好像也不会怎么样 那么请问你在魔王给他们的数字是`00`,`01`,`10`,`11`这四种情况下,**至少有一人猜对**的可能是多少? 题解:根据魔王给的这四种可能,我们可以看出,魔王给的两个数字只可能相同或者不同,所以这两个人只要一个人猜另一个数和自己相同,一个人猜另一个数字和自己不同,这样他们就一定能赢.概率就是`1.00` 代码: ```cpp #include <cstdio> int main() { puts("1.00"); puts("1.00"); puts("1.00"); puts("1.00"); } ``` --- ## [1002 人类史上最大最好的希望事件](http://acm.hdu.edu.cn/showproblem.php?pid=6462) 题意:多组数据Q,接下来Q组询问,每组询问给四个数a,b,c,d. 我们假设$fib(n)$表示斐波那契数列第n项,对于每组询问,输出 $$ {\sum_{i=min(4a+b+1,4c+d+1)}^{max(4a+b+1,4c+d+1)} {fib(i)^2}}\pmod {192600817} $$ 了解了题目接下来的的方案就好确定了。 因为`4a+b+1`的范围不会大于40004,所以我们就直接`O(n)`跑一遍50000的斐波那契数列,求解斐波那契数列的平方和有公式: $$ {\sum_{i=1}^n fib(i)^2} = fib(n)*fib(n+1) $$ 所以最后代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; const ll mod=192600817; ll fi[50000]={1,1}; ll calc(ll n) { return fi[n]*fi[n-1]%mod; } int main() { for(int i = 2;i < 50000;i++){ fi[i]=fi[i-1]+fi[i-2]; fi[i]%=mod; } int q; while(~scanf("%d",&q)) { while(q--) { ll a,b,c,d; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); a=a*4+1+b; c=c*4+1+d; if(c<a) swap(a,c); printf("%lld\n",(calc(c)-calc(a-1)+mod)%mod); } } return 0; } ``` --- ## [1003 超级无敌简单题](http://acm.hdu.edu.cn/showproblem.php?pid=6463) 根据题目给定的规则,我们可以很清楚的看到6位数的数字,经过一轮变换之后就算是`999999`也会变成6*9*9=486<1000,所以我们只要先暴力跑一遍`1~1,000,000`的鸽子数,最后输入输出就好了. 代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; int gz[1000100]={0,2,1,1,1,1,1,2}; int calc(int n) { int ans=0; while(n){ ans+=(n%10)*(n%10); n/=10; } return ans; } bool dfs(int n) { //printf("now calc %d\n",n); if(gz[n]) return gz[n]-1; int c=calc(n); if(c==1) {gz[n]=2;return true;} else return (gz[n]=dfs(c)+1)-1; } vector<ll> sd; int main() { sd.push_back(1); sd.push_back(7); for(int i = 8;i < 1000000;i++){ if(dfs(i)) sd.push_back(i); //if(i==150000) puts("yes"); } int q,k; scanf("%d",&q); while(q--) { scanf("%d",&k); printf("%lld\n",sd[k-1]); } return 0; } ``` --- ## [1004 免费送气球](http://acm.hdu.edu.cn/showproblem.php?pid=6464) **因为这题目我没有写出来,只问队友要了一份,所以暂时这题没有解析** 大致方向:树状数组加二分 代码: ```cpp #include<bits/stdc++.h> #define inf 0x3f3f3f typedef long long ll; using namespace std; struct P{ ll ty,se,fi; }p[100010]; ll a[100010],sum[100010]; const ll mod=1000000007; int cnt; inline ll lowb(ll x){ return x&(-x); } map<int,int>mp; inline ll finda(ll x){ ll ans=0; while(x){ ans+=a[x]; x-=lowb(x); } return ans; } inline void upa(ll x,ll z){ while(x<=cnt){ a[x]=a[x]+z; x+=lowb(x); } return; } inline ll finds(ll x){ ll ans=0; while(x){ ans=(ans+sum[x])%mod; x-=lowb(x); } return ans; } inline void ups(ll x,ll z){ while(x<=cnt){ sum[x]=(sum[x]+z)%mod; x+=lowb(x); } return; } ll R; inline bool ck(int x){ ll num=finda(x); return num>=R; } ll ef(ll l,ll r){ //cout<<l<<" "<<r<<" "<<(l+r)/2<<" "<<ck((l+r)/2)<<endl; if(l==r)return l; if(l==r-1){ if(ck(l))return l; return r; } ll mid=(l+r)/2; if(ck(mid))return ef(l,mid); return ef(mid+1,r); } int f[100010]; ll query(ll x){ if(x==0)return 0; R=x; ll l=ef(1,cnt)-1; ll now=f[l+1]; /*while(x==8){ cin>>l; cout<<finda(l)<<endl; }*/ //if(x==8)cout<<x<<" "<<l<<" "<<now<<" "<<finda(2)<<endl; return (finds(l)+(x-finda(l))*now%mod)%mod; } int main(){ int n; scanf("%d",&n); for(ll i=1;i<=n;i++){ scanf("%lld%lld%lld",&p[i].ty,&p[i].fi,&p[i].se); if(p[i].ty==1)mp[p[i].se]=1; } for(auto x:mp){ f[++cnt]=x.first; mp[x.first]=cnt; //cout<<x.first<<" "<<mp[x.first]<<endl; } //cout<<cnt<<endl; for(int i=1;i<=n;i++){ //cout<<p[i].ty<<" "<<p[i].fi<<" "<<p[i].se<<endl; if(p[i].ty==1){ int x=mp[p[i].se]; upa(x,p[i].fi); ups(x,p[i].fi*p[i].se%mod); } else { ll l=query(p[i].fi-1),r=query(p[i].se); ll ans=((r-l)%mod+mod)%mod; printf("%lld\n",ans); } } return 0; } ``` --- ## [1005 水题](http://acm.hdu.edu.cn/showproblem.php?pid=6465) 和网上的验题人题解用高斯消元做有点不同,我这题用的是向量做的,而且也觉得这个写法比较简单.本来是在最后一个小时的时候想到了要这样做,但是无奈写错了一个地方,比完5分钟才debug完AC的,确实很可惜.另外,批评百度百科,上面的公式都是错的,早知道自己手推也许就能在规定时间内AC的. 不扯那么多了,题目给你了变换前的三角形坐标和变换后的三角形坐标,保证了这三点不是在同一条直线上,我们知道,平面上的一对不平行的向量可以作为一组基底,表示平面上的任何一个向量.而位置又是相对的,假设变换前的坐标是$A_1,B_1,C_1,D_1$,变换后的坐标是$A_2,B_2,C_2,D_2$,求解的坐标是`点D`,在变换前,我们可以用向量$\vec{A_1B_1}$,$\vec{A_1C_1}$表示向量$\vec{A_1D_1}$,有: $$ \vec{A_1D_1}={\alpha\vec{A_1B_1}+\beta\vec{A_1C_1}} $$ 这里我们$A_1,B_1,C_1,D_1$四个点的坐标都是知道的,就可以得到一个二元一次方程组,得到这里的$\alpha\ \beta$ > 该死的百度,百科里面的公式都是错的! 变换后的A,B,C,D四个点的的相对位置是不变的,所以还有 $$ \vec{A_2D_2}={\alpha\vec{A_2B_2}+\beta\vec{A_2C_2}} $$ 而在这里我们$\alpha\ \beta\ A_2\ B_2\ C_2$的坐标都是知道,这样也就可以求出变换后的`D点`坐标啦. 代码: ``` /* *Team hhu_6814 *Author big_yellow_doge */ #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; struct Vec{ double a,b; }va,vb,vd,ve; Vec calc(Vec a,Vec b,Vec c) { Vec ans; //printf("now calc is %.2f %.2f %.2f %.2f %.2f %.2f\n",a.a,a.b,b.a,b.b,c.a,c.b); ans.b=(a.a*c.b-a.b*c.a)/(a.a*b.b-b.a*a.b); ans.a=(b.a*c.b-b.b*c.a)/(b.a*a.b-b.b*a.a); return ans; } void Mul(Vec a,Vec b,double ba,double bb,Vec mt) { ba+=mt.a*a.a; bb+=mt.a*a.b; ba+=mt.b*b.a; bb+=mt.b*b.b; printf("%.2f %.2f\n",ba,bb); } int main() { int t; scanf("%d",&t); while(t--) { double x1,y1,x2,y2,x3,y3; double x4,y4,x5,y5,x6,y6; scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3); scanf("%lf%lf%lf%lf%lf%lf",&x4,&y4,&x5,&y5,&x6,&y6); va.a=x2-x1; va.b=y2-y1; vb.a=x3-x1; vb.b=y3-y1; vd.a=x5-x4; vd.b=y5-y4; ve.a=x6-x4; ve.b=y6-y4; int q; scanf("%d",&q); while(q--) { double x,y; scanf("%lf%lf",&x,&y); Vec vc; vc.a=x-x1; vc.b=y-y1; vc=calc(va,vb,vc); //printf("calc = %.2f %.2f \n",vc.a,vc.b); Mul(vd,ve,x4,y4,vc); } } return 0; } ``` --- ## [1006 清一色](http://acm.hdu.edu.cn/showproblem.php?pid=6466) ## 这个又是一道打麻将题,暂时没补,请参考出题人题解. --- ## [1007 简单数学题](http://acm.hdu.edu.cn/showproblem.php?pid=6467) ## 比赛的时候是推了一半的公式,然后OEIS了一下过去的,下面给出严格的推导过程 $$ \begin{split} F(n)&=\sum_{i=1}^n{(i*\sum_{j=i}^n C_j^i)} \\ &=\sum_{i=1}^n{\sum_{j=i}^n {i*C_j^i}} \\ &=\sum_{j=1}^n{\sum_{i=1}^j {i*C_j^i}} \\ &=\sum_{j=1}^n{j*2^{n-1}} \end{split} $$ 由此得到 $$ F(n)= \begin{cases} 1, &n=1 \\ F(n-1)+n*2^{n-1},&n>1 \end{cases} $$ 继续计算: $$ \begin{split} F(n)-F(n-1)*2^n &= F(n-1)-(n-2)*2^{n-1} \\ F(n)-(n-1)*2^n &= F(1)-(1-1)*2=1 \\ F(n) &= (n-1)*2^{n-1}+1 \end{split} $$ 得到了最后的公式: $F(n)=(n-1)*2^{n-1}+1$这样就好做了,这样也就是一个快速幂就能解决的问题啦. 代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; const ll mod=1e9+7; ll qmod(ll p) { ll ans=1; ll a=2; while(p) { if(p&1){ ans*=a; ans%=mod; } p>>=1; a*=a; a%=mod; } return ans; } int main() { ll n; while(scanf("%lld",&n)!=EOF) { printf("%lld\n",(n-1)%mod*qmod(n)%mod+1%mod); } return 0; } ``` --- ## [1008 zyb的面试](http://acm.hdu.edu.cn/showproblem.php?pid=6468) 题目意思:`将1-n的数字按字典序排序`,输出排序后的第m个数字. ~~印象中这题是在牛客还是哪里写过~~套的网上的代码 代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; int getNum(int n, int k) { int base = 1, sum = 0; while (n >= base * (k+1) -1) { sum += base; base *= 10; } if (n >= base * k) sum += n - base * k + 1; return sum; } int ans = 0; void getMth(int n, int m, int& k, int cur) { if (++k == m) { ans = cur; return; } for (int i = 0; i <= 9; i++) { int t = cur * 10 + i; if (t <= n) getMth(n, m, k, t); if (k >= m) return; } } int main() { int m, n, k = 0,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); k=0;int i = 1; for (; i <= 9; i++) { int num = getNum(n, i); if (num < m) m -= num; else break; } getMth(n, m, k, i); printf("%d\n",ans); ans=0; } return 0; } ``` --- ## [1009 故事](http://acm.hdu.edu.cn/showproblem.php?pid=6469) 想法是二分,但是没有想到要咋check 写法请参考出题人或者验题人的题解 --- ## [1010 Count](http://acm.hdu.edu.cn/showproblem.php?pid=6470) 这题目也没什么好说的,就是一个矩阵快速幂的模板题,在处理$n^3$的时候要把它分成$n^2$,n,1来处理,最后就是一个6*6大小的转移矩阵. $$ { \begin{bmatrix} F(n)\\ F(n-1)\\ n^3\\ n^2\\ n\\ 1 \end{bmatrix} }={ \begin{bmatrix} 1&2&1&3&3&1\\ 1&0&0&0&0&0\\ 1&0&0&3&3&1\\ 0&0&0&1&2&1\\ 0&0&0&0&1&1\\ 0&0&0&0&0&1 \end{bmatrix} }^{n-2}{ \begin{bmatrix} F(2)\\ F(1)\\ 8\\ 4\\ 2\\ 1 \end{bmatrix} } $$ 参考代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> typedef long long ll; using namespace std; const int mod=123456789; ll a[10][10],ans[10][10],o[10][10]; void mul(ll a[][10],ll b[][10],ll ans[][10]){ ll c[10][10]; for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++)c[i][j]=0; } for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++){ for(int k=1;k<=6;k++){ c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod; } } } for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++)ans[i][j]=c[i][j]; } } void qmod(ll ans[][10],ll b){ ll c[10][10]; for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++){ ans[i][j]=0; c[i][j]=a[i][j]; if(i==j)ans[i][j]=1; } } while(b){ if(b&1)mul(ans,c,ans); b>>=1; mul(c,c,c); } } void pr(int ans[][10]){ for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++){ cout<<ans[i][j]<<" "; } cout<<endl; } } int main(){ int n; a[1][1]=1;a[1][2]=2;a[1][3]=1;a[1][4]=3; a[1][5]=3;a[1][6]=1; a[2][1]=1; a[3][3]=1;a[3][4]=3;a[3][5]=3;a[3][6]=1; a[4][4]=1;a[4][5]=2;a[4][6]=1; a[5][5]=1;a[5][6]=1; a[6][6]=1; o[1][1]=2;o[2][1]=1;o[3][1]=8;o[4][1]=4;o[5][1]=2;o[6][1]=1; scanf("%d",&n); while(n--){ ll t; scanf("%lld",&t); qmod(ans,t-2); mul(ans,o,ans); //pr(ans); printf("%lld\n",ans[1][1]); } return 0; } ``` Loading... **原题地址：** [原题地址](http://acm.hdu.edu.cn/search.php?field=problem&key=%A1%B0%D7%D6%BD%DA%CC%F8%B6%AF-%CE%C4%D4%B6%D6%AA%D0%D0%B1%AD%A1%B1%B9%E3%B6%AB%B9%A4%D2%B5%B4%F3%D1%A7%B5%DA%CA%AE%CB%C4%BD%EC%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC&source=1&searchmode=source) **[出题人题解](https://hodam.top/myfile/acm/gdut14/solution.pdf)** **[验题人题解](https://hodam.top/myfile/acm/gdut14/solution2.pdf)** **总的来说这里的题目代码都不是那么的长，有些可能要点思维** --- ## [1001 hzy 和zsl 的生存挑战](http://acm.hdu.edu.cn/showproblem.php?pid=6461) 现在有两个人,他们被分开在了两个房间,魔王**各给他们了一个数字(可能是0或者1)** 现在要求他们两个人去猜魔王给他们的这两个数字分别是什么(或者说去猜对方拿到的数字是什么),两个人在进入房间之前是知道这件事的,但是他们在给了数字之后是**完全无法联系的**.魔王要求至少有一个人要猜对,否则他们就会 > 好像也不会怎么样 那么请问你在魔王给他们的数字是`00`,`01`,`10`,`11`这四种情况下,**至少有一人猜对**的可能是多少? 题解:根据魔王给的这四种可能,我们可以看出,魔王给的两个数字只可能相同或者不同,所以这两个人只要一个人猜另一个数和自己相同,一个人猜另一个数字和自己不同,这样他们就一定能赢.概率就是`1.00` 代码: ```cpp #include <cstdio> int main() { puts("1.00"); puts("1.00"); puts("1.00"); puts("1.00"); } ``` --- ## [1002 人类史上最大最好的希望事件](http://acm.hdu.edu.cn/showproblem.php?pid=6462) 题意:多组数据Q,接下来Q组询问,每组询问给四个数a,b,c,d. 我们假设$fib(n)$表示斐波那契数列第n项,对于每组询问,输出 $$ {\sum_{i=min(4a+b+1,4c+d+1)}^{max(4a+b+1,4c+d+1)} {fib(i)^2}}\pmod {192600817} $$ 了解了题目接下来的的方案就好确定了。 因为`4a+b+1`的范围不会大于40004,所以我们就直接`O(n)`跑一遍50000的斐波那契数列,求解斐波那契数列的平方和有公式: $$ {\sum_{i=1}^n fib(i)^2} = fib(n)*fib(n+1) $$ 所以最后代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; const ll mod=192600817; ll fi[50000]={1,1}; ll calc(ll n) { return fi[n]*fi[n-1]%mod; } int main() { for(int i = 2;i < 50000;i++){ fi[i]=fi[i-1]+fi[i-2]; fi[i]%=mod; } int q; while(~scanf("%d",&q)) { while(q--) { ll a,b,c,d; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); a=a*4+1+b; c=c*4+1+d; if(c<a) swap(a,c); printf("%lld\n",(calc(c)-calc(a-1)+mod)%mod); } } return 0; } ``` --- ## [1003 超级无敌简单题](http://acm.hdu.edu.cn/showproblem.php?pid=6463) 根据题目给定的规则,我们可以很清楚的看到6位数的数字,经过一轮变换之后就算是`999999`也会变成6*9*9=486<1000,所以我们只要先暴力跑一遍`1~1,000,000`的鸽子数,最后输入输出就好了. 代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; int gz[1000100]={0,2,1,1,1,1,1,2}; int calc(int n) { int ans=0; while(n){ ans+=(n%10)*(n%10); n/=10; } return ans; } bool dfs(int n) { //printf("now calc %d\n",n); if(gz[n]) return gz[n]-1; int c=calc(n); if(c==1) {gz[n]=2;return true;} else return (gz[n]=dfs(c)+1)-1; } vector<ll> sd; int main() { sd.push_back(1); sd.push_back(7); for(int i = 8;i < 1000000;i++){ if(dfs(i)) sd.push_back(i); //if(i==150000) puts("yes"); } int q,k; scanf("%d",&q); while(q--) { scanf("%d",&k); printf("%lld\n",sd[k-1]); } return 0; } ``` --- ## [1004 免费送气球](http://acm.hdu.edu.cn/showproblem.php?pid=6464) **因为这题目我没有写出来,只问队友要了一份,所以暂时这题没有解析** 大致方向:树状数组加二分 代码: ```cpp #include<bits/stdc++.h> #define inf 0x3f3f3f typedef long long ll; using namespace std; struct P{ ll ty,se,fi; }p[100010]; ll a[100010],sum[100010]; const ll mod=1000000007; int cnt; inline ll lowb(ll x){ return x&(-x); } map<int,int>mp; inline ll finda(ll x){ ll ans=0; while(x){ ans+=a[x]; x-=lowb(x); } return ans; } inline void upa(ll x,ll z){ while(x<=cnt){ a[x]=a[x]+z; x+=lowb(x); } return; } inline ll finds(ll x){ ll ans=0; while(x){ ans=(ans+sum[x])%mod; x-=lowb(x); } return ans; } inline void ups(ll x,ll z){ while(x<=cnt){ sum[x]=(sum[x]+z)%mod; x+=lowb(x); } return; } ll R; inline bool ck(int x){ ll num=finda(x); return num>=R; } ll ef(ll l,ll r){ //cout<<l<<" "<<r<<" "<<(l+r)/2<<" "<<ck((l+r)/2)<<endl; if(l==r)return l; if(l==r-1){ if(ck(l))return l; return r; } ll mid=(l+r)/2; if(ck(mid))return ef(l,mid); return ef(mid+1,r); } int f[100010]; ll query(ll x){ if(x==0)return 0; R=x; ll l=ef(1,cnt)-1; ll now=f[l+1]; /*while(x==8){ cin>>l; cout<<finda(l)<<endl; }*/ //if(x==8)cout<<x<<" "<<l<<" "<<now<<" "<<finda(2)<<endl; return (finds(l)+(x-finda(l))*now%mod)%mod; } int main(){ int n; scanf("%d",&n); for(ll i=1;i<=n;i++){ scanf("%lld%lld%lld",&p[i].ty,&p[i].fi,&p[i].se); if(p[i].ty==1)mp[p[i].se]=1; } for(auto x:mp){ f[++cnt]=x.first; mp[x.first]=cnt; //cout<<x.first<<" "<<mp[x.first]<<endl; } //cout<<cnt<<endl; for(int i=1;i<=n;i++){ //cout<<p[i].ty<<" "<<p[i].fi<<" "<<p[i].se<<endl; if(p[i].ty==1){ int x=mp[p[i].se]; upa(x,p[i].fi); ups(x,p[i].fi*p[i].se%mod); } else { ll l=query(p[i].fi-1),r=query(p[i].se); ll ans=((r-l)%mod+mod)%mod; printf("%lld\n",ans); } } return 0; } ``` --- ## [1005 水题](http://acm.hdu.edu.cn/showproblem.php?pid=6465) 和网上的验题人题解用高斯消元做有点不同,我这题用的是向量做的,而且也觉得这个写法比较简单.本来是在最后一个小时的时候想到了要这样做,但是无奈写错了一个地方,比完5分钟才debug完AC的,确实很可惜.另外,批评百度百科,上面的公式都是错的,早知道自己手推也许就能在规定时间内AC的. 不扯那么多了,题目给你了变换前的三角形坐标和变换后的三角形坐标,保证了这三点不是在同一条直线上,我们知道,平面上的一对不平行的向量可以作为一组基底,表示平面上的任何一个向量.而位置又是相对的,假设变换前的坐标是$A_1,B_1,C_1,D_1$,变换后的坐标是$A_2,B_2,C_2,D_2$,求解的坐标是`点D`,在变换前,我们可以用向量$\vec{A_1B_1}$,$\vec{A_1C_1}$表示向量$\vec{A_1D_1}$,有: $$ \vec{A_1D_1}={\alpha\vec{A_1B_1}+\beta\vec{A_1C_1}} $$ 这里我们$A_1,B_1,C_1,D_1$四个点的坐标都是知道的,就可以得到一个二元一次方程组,得到这里的$\alpha\ \beta$ > 该死的百度,百科里面的公式都是错的! 变换后的A,B,C,D四个点的的相对位置是不变的,所以还有 $$ \vec{A_2D_2}={\alpha\vec{A_2B_2}+\beta\vec{A_2C_2}} $$ 而在这里我们$\alpha\ \beta\ A_2\ B_2\ C_2$的坐标都是知道,这样也就可以求出变换后的`D点`坐标啦. 代码: ``` /* *Team hhu_6814 *Author big_yellow_doge */ #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; struct Vec{ double a,b; }va,vb,vd,ve; Vec calc(Vec a,Vec b,Vec c) { Vec ans; //printf("now calc is %.2f %.2f %.2f %.2f %.2f %.2f\n",a.a,a.b,b.a,b.b,c.a,c.b); ans.b=(a.a*c.b-a.b*c.a)/(a.a*b.b-b.a*a.b); ans.a=(b.a*c.b-b.b*c.a)/(b.a*a.b-b.b*a.a); return ans; } void Mul(Vec a,Vec b,double ba,double bb,Vec mt) { ba+=mt.a*a.a; bb+=mt.a*a.b; ba+=mt.b*b.a; bb+=mt.b*b.b; printf("%.2f %.2f\n",ba,bb); } int main() { int t; scanf("%d",&t); while(t--) { double x1,y1,x2,y2,x3,y3; double x4,y4,x5,y5,x6,y6; scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3); scanf("%lf%lf%lf%lf%lf%lf",&x4,&y4,&x5,&y5,&x6,&y6); va.a=x2-x1; va.b=y2-y1; vb.a=x3-x1; vb.b=y3-y1; vd.a=x5-x4; vd.b=y5-y4; ve.a=x6-x4; ve.b=y6-y4; int q; scanf("%d",&q); while(q--) { double x,y; scanf("%lf%lf",&x,&y); Vec vc; vc.a=x-x1; vc.b=y-y1; vc=calc(va,vb,vc); //printf("calc = %.2f %.2f \n",vc.a,vc.b); Mul(vd,ve,x4,y4,vc); } } return 0; } ``` --- ## [1006 清一色](http://acm.hdu.edu.cn/showproblem.php?pid=6466) ## 这个又是一道打麻将题,暂时没补,请参考出题人题解. --- ## [1007 简单数学题](http://acm.hdu.edu.cn/showproblem.php?pid=6467) ## 比赛的时候是推了一半的公式,然后OEIS了一下过去的,下面给出严格的推导过程 $$ \begin{split} F(n)&=\sum_{i=1}^n{(i*\sum_{j=i}^n C_j^i)} \\ &=\sum_{i=1}^n{\sum_{j=i}^n {i*C_j^i}} \\ &=\sum_{j=1}^n{\sum_{i=1}^j {i*C_j^i}} \\ &=\sum_{j=1}^n{j*2^{n-1}} \end{split} $$ 由此得到 $$ F(n)= \begin{cases} 1, &n=1 \\ F(n-1)+n*2^{n-1},&n>1 \end{cases} $$ 继续计算: $$ \begin{split} F(n)-F(n-1)*2^n &= F(n-1)-(n-2)*2^{n-1} \\ F(n)-(n-1)*2^n &= F(1)-(1-1)*2=1 \\ F(n) &= (n-1)*2^{n-1}+1 \end{split} $$ 得到了最后的公式: $F(n)=(n-1)*2^{n-1}+1$这样就好做了,这样也就是一个快速幂就能解决的问题啦. 代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; const ll mod=1e9+7; ll qmod(ll p) { ll ans=1; ll a=2; while(p) { if(p&1){ ans*=a; ans%=mod; } p>>=1; a*=a; a%=mod; } return ans; } int main() { ll n; while(scanf("%lld",&n)!=EOF) { printf("%lld\n",(n-1)%mod*qmod(n)%mod+1%mod); } return 0; } ``` --- ## [1008 zyb的面试](http://acm.hdu.edu.cn/showproblem.php?pid=6468) 题目意思:`将1-n的数字按字典序排序`,输出排序后的第m个数字. ~~印象中这题是在牛客还是哪里写过~~套的网上的代码 代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> using namespace std; //ios::sync_with_stdio(false); const int MINF = 0x7fffffff; const int INF = 0x3f3f3f3f; const int Maxn = 1e5+5; typedef long long ll; int getNum(int n, int k) { int base = 1, sum = 0; while (n >= base * (k+1) -1) { sum += base; base *= 10; } if (n >= base * k) sum += n - base * k + 1; return sum; } int ans = 0; void getMth(int n, int m, int& k, int cur) { if (++k == m) { ans = cur; return; } for (int i = 0; i <= 9; i++) { int t = cur * 10 + i; if (t <= n) getMth(n, m, k, t); if (k >= m) return; } } int main() { int m, n, k = 0,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); k=0;int i = 1; for (; i <= 9; i++) { int num = getNum(n, i); if (num < m) m -= num; else break; } getMth(n, m, k, i); printf("%d\n",ans); ans=0; } return 0; } ``` --- ## [1009 故事](http://acm.hdu.edu.cn/showproblem.php?pid=6469) 想法是二分,但是没有想到要咋check 写法请参考出题人或者验题人的题解 --- ## [1010 Count](http://acm.hdu.edu.cn/showproblem.php?pid=6470) 这题目也没什么好说的,就是一个矩阵快速幂的模板题,在处理$n^3$的时候要把它分成$n^2$,n,1来处理,最后就是一个6*6大小的转移矩阵. $$ { \begin{bmatrix} F(n)\\ F(n-1)\\ n^3\\ n^2\\ n\\ 1 \end{bmatrix} }={ \begin{bmatrix} 1&2&1&3&3&1\\ 1&0&0&0&0&0\\ 1&0&0&3&3&1\\ 0&0&0&1&2&1\\ 0&0&0&0&1&1\\ 0&0&0&0&0&1 \end{bmatrix} }^{n-2}{ \begin{bmatrix} F(2)\\ F(1)\\ 8\\ 4\\ 2\\ 1 \end{bmatrix} } $$ 参考代码: ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <string.h> #include <queue> #include <map> #include <stack> #include <vector> #include <set> #include <list> typedef long long ll; using namespace std; const int mod=123456789; ll a[10][10],ans[10][10],o[10][10]; void mul(ll a[][10],ll b[][10],ll ans[][10]){ ll c[10][10]; for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++)c[i][j]=0; } for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++){ for(int k=1;k<=6;k++){ c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod; } } } for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++)ans[i][j]=c[i][j]; } } void qmod(ll ans[][10],ll b){ ll c[10][10]; for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++){ ans[i][j]=0; c[i][j]=a[i][j]; if(i==j)ans[i][j]=1; } } while(b){ if(b&1)mul(ans,c,ans); b>>=1; mul(c,c,c); } } void pr(int ans[][10]){ for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++){ cout<<ans[i][j]<<" "; } cout<<endl; } } int main(){ int n; a[1][1]=1;a[1][2]=2;a[1][3]=1;a[1][4]=3; a[1][5]=3;a[1][6]=1; a[2][1]=1; a[3][3]=1;a[3][4]=3;a[3][5]=3;a[3][6]=1; a[4][4]=1;a[4][5]=2;a[4][6]=1; a[5][5]=1;a[5][6]=1; a[6][6]=1; o[1][1]=2;o[2][1]=1;o[3][1]=8;o[4][1]=4;o[5][1]=2;o[6][1]=1; scanf("%d",&n); while(n--){ ll t; scanf("%lld",&t); qmod(ans,t-2); mul(ans,o,ans); //pr(ans); printf("%lld\n",ans[1][1]); } return 0; } ``` Last modification：August 9, 2026 © Allow specification reprint Support Appreciate the author Like 如果觉得我的文章对你有用，请随意赞赏
One comment
评论测试