广东工业大学第十四届程序设计竞赛 个人题解 (1,2,3,7,8,10)
1001 hzy 和zsl 的生存挑战 (hdu6461)
两个人都知道一个数，zsl知道A，hzy知道B，假设zsl猜另一个数为A，hzy猜另一个数为B^1
那么zsl的答案是AA，hzy的答案是B(B^1) 可以保证有且仅有一个人猜对（手动模拟一下就知道了）
为啥自己交了一次cout<<1.00<<endl ???
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
ios :: sync_with_stdio(false);
for(int i=1;i<=4;i++){
cout<<"1.00"<<endl;
}
return 0;
}
1002 人类史上最大最好的希望事件 (hdu6462)
题意就是求斐波那契数（每一项都平方）的i项到j项的和
直接前缀和弄弄
只是个水题我居然比赛没去写，（考语文???）
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 192600817
const int maxn=4e4+10;
LL ans[maxn+5]={0,1};
LL fb[maxn+5]={0,1};
int main(){
ios::sync_with_stdio(false);
for(int i=2;i<=maxn;i++){
fb[i]=(fb[i-1]+fb[i-2])%mod;
ans[i]=(ans[i-1]+fb[i]*fb[i]%mod)%mod;
}
int q;
while(cin>>q)
while(q--){
int a,c,b,d;
cin>>a>>b>>c>>d;
int s,e;
s=a*4+b+1;
e=c*4+d+1;
if(s>e) swap(s,e);
cout<<(ans[e]-ans[s-1]+mod)%mod<<endl;
}
return 0;
}1003 超级无敌简单题(hdu6463)
我的思路：
从一个数i开始dfs() （用vis记录是否走过），
如果这个数是鸽子数，那么经过若干步转换成1，那么将他曾经转换成过的数（也就是路径上的数）全都标记成鸽子数。
如果这个数不是鸽子数，那么他一定会有循环节（因为将∑(每位的数字的平方) 有一个上界），当转换成标记过的数时停止，将路径上的全部标记为不是鸽子数。
大家后来告诉循环次数有上界（ :
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn=2000000;
bool vis[maxn+5];
int path[maxn+5]; //记录路径
bool y[maxn+5],no[maxn+5]; //y(鸽子数） no（不是鸽子数）
int apart(int i){ //转换
int re=0;
while(i){
re=re+(i%10)*(i%10);
i=i/10;
}
return re;
}
void jud(int i){ //dfs()
int p=0;
while(vis[i]!=1){
vis[i]=1;
path[++p]=i;
i=apart(i);
}
if(y[i]==1){
for(int i=1;i<=p;i++){
y[path[i]]=1;
}
}
else {
for(int i=1;i<=p;i++){
no[path[i]]=1;
}
}
}
int main(){
ios::sync_with_stdio(false);
vis[1]=1;
y[1]=1;
for(int i=1;i<=maxn;i++){ //maxn是上界（不断测出来的）
jud(i);
}
int p=0; //记录鸽子数的数目
for(int i=1;i<=maxn;i++){
if(y[i]) path[++p]=i;
}
int q;
cin>>q;
while(q--){
int x;cin>>x;
cout<<path[x]<<endl;
}
return 0;
}
1007 简单数学题 (hdu6467)
真丶哭唧唧 （矩阵快速幂TLE了4发，多了矩阵边长的三次方，卡的死死的，）
其实是一个推式子的题
F(n)=(n-1)*2^n+1
理了理思路（我的解法）
题解DL的解法（好像有点小错误）：
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 1000000007
LL pow_mod(LL a, LL n, LL m)
{
LL ans = 1;
while(n){
if(n&1){
ans = (ans * a) % m;
}
a = (a * a) % m;
n >>= 1;
}
return ans;
}
int main(){
LL n;ios::sync_with_stdio(false);
while(cin>>n){
LL x=pow_mod(2,n,mod);
x=x+mod;x=x%mod;
x=x*((n-1)%mod)+1;
x=x+mod;x=x%mod;
cout<<x<<endl;
}
return 0;
}1008 zyb的面试(hdu6468)
赛时在写O(n*T)的代码，虽然没交，但是感觉肯定卡不过。。赛后补
正解：
（假装）建立如图的树
即先序遍历到第k个数就是答案，（但是老老实实遍历肯定超时）
那可以把这个树看成一个图，就相当于在图中走路（从1到答案ans）
记录代价为s（当s==k时就到了终点）
从ans=1（左上角）开始，向下走，ans=ans*10，向右走ans=ans+1。
向下走的代价为1，s+1，因为排好序之后相邻。
向右走时，假设代价为x，如果x+s<=k，那么就直接像右走。问题就是求x：
枚举位数，考虑与n的关系就可以求出x（难点）。
因为是向下或者向右走，所以最长路径是位数*10。总复杂度就是O（T*6*10*6） 这个复杂度很低了
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 1000000007
int pten[10]={1}; //pow(10,i)
int wein;
int cwei(int i){ //计算i的位数
int re=0;
while(i){
re++;
i=i/10;
}
return re;
}
int cleft(int now,int n){ //计算向右走的代价
int weinow=cwei(now);
int re=0;
for(int i=weinow+1;i<wein;i++){
re=re+pten[i-weinow];
now=now*10;
}
now=now*10;
int x=min(n-now+1,pten[wein-weinow]); //n对代价的影响
if(x>0) re=re+x;
return re+1;
}
int main(){
ios::sync_with_stdio(false);
for(int i=1;i<=8;i++){
pten[i]=pten[i-1]*10;
}
int T;
cin>>T;
while(T--){
int n,k;
cin>>n>>k;
wein=cwei(n);
int ans=1;
k--;
while(k>0){
int x=cleft(ans,n);
if(x<=k){ //向左走
k=k-x;
ans++;
}
else { //向右走
k--;
ans=ans*10;
}
}
cout<<ans<<endl;
}
return 0;
}
1010 Count (hdu6470)
前几年沈阳icpc的题 这题将i^4变成了i^3
题解（直接看最后一个样题 ）：https://blog.csdn.net/qq_41730604/article/details/87993405
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define mod 123456789
#define N 20
/* ( x x x x x )^n
( x x x x x )
(x x x x x) * ( x x x x x )
( x x x x x )
( x x x x x ) */
LL nn;
struct mat{
LL m[8][8];
};
mat matmul(mat a,mat b){
mat re;
memset(re.m,0,sizeof(re.m));
for(int i=1;i<=nn;i++){
for(int j=1;j<=nn;j++){
for(int k=1;k<=nn;k++){
re.m[i][j]=(re.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
}
}
return re;
}
mat quickmod(LL x,mat jin){
mat re;
memset(re.m,0,sizeof(re.m));
for(int i=1;i<=nn;i++) re.m[i][i]=1;
while(x){
if(x&1)
re=matmul(re,jin);
x=x>>1;
jin=matmul(jin,jin);
}
return re;
}
mat init(){
mat x;
x.m[1][1]=1;x.m[1][2]=0;x.m[1][3]=1;x.m[1][4]=0;x.m[1][5]=0;x.m[1][6]=0;x.m[1][7]=0;
x.m[2][1]=0;x.m[2][2]=0;x.m[2][3]=0;x.m[2][4]=0;x.m[2][5]=0;x.m[2][6]=0;x.m[2][7]=0;
x.m[3][1]=2;x.m[3][2]=1;x.m[3][3]=0;x.m[3][4]=0;x.m[3][5]=0;x.m[3][6]=0;x.m[3][7]=0;
x.m[4][1]=1;x.m[4][2]=0;x.m[4][3]=0;x.m[4][4]=1;x.m[4][5]=0;x.m[4][6]=0;x.m[4][7]=0;
x.m[5][1]=3;x.m[5][2]=0;x.m[5][3]=0;x.m[5][4]=3;x.m[5][5]=1;x.m[5][6]=0;x.m[5][7]=0;
x.m[6][1]=3;x.m[6][2]=0;x.m[6][3]=0;x.m[6][4]=3;x.m[6][5]=2;x.m[6][6]=1;x.m[6][7]=0;
x.m[7][1]=1;x.m[7][2]=0;x.m[7][3]=0;x.m[7][4]=1;x.m[7][5]=1;x.m[7][6]=1;x.m[7][7]=1;
return x;
}
int main(){
ios :: sync_with_stdio(false);
int T;cin>>T;
while(T--){
LL n;
cin>>n;
if(n==1){
cout<<1;continue;
}
if(n==2){
cout<<2;continue;
}
nn=7;
mat x;memset(x.m,0,sizeof(x.m));
x.m[1][1]=31;x.m[1][2]=1;x.m[1][3]=2;x.m[1][4]=27;x.m[1][5]=9;x.m[1][6]=3;x.m[1][7]=1;
mat t=quickmod(n-3,init());
x=matmul(x,t);
cout<<x.m[1][1]<<endl;
}
return 0;
}