暑假训练之gym

暑假训练之gym"/>

暑假训练之gym

题目链接：

题解：A、C、E、F、H、K、 J、L

A. 两只脑斧

签到题，按照题目图片直接做就可以了2、4、6、7 是吸，1、3、5 是吹，0 是停止

AC代码：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e2+10;
int a[N];
char s[5]; 
vector<char>ans;int main()
{int n;cin>>n;rep(i,1,n){cin>>s+1;int d=s[1]-'0';if(d==0) ans.pb('X');else if(d==1||d==3||d==5) ans.pb('E');else ans.pb('I');}for(int i=0;i<ans.size();++i) printf("%c",ans[i]);
}

C. 赛尔逵传说

题意挺难懂的，，我也看了很久，还wa了几发。

后来直接贪心，把攻击力从大到小排序（将血量低于玩家攻击力已经排除了）

若当前怪物血量大于自己的攻击力，那么尽可能的吃果子，使得玩家能一次秒杀这个怪物。

若果子不够了，那就按照最普通的方法进行杀怪，减血，，一直处理到最后就好了。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{ll d,x,f;
}a[N];
int n,cnt;
ll k,c;
bool cmp(node a,node b){return a.x>b.x;
}
int main(){cin>>n>>k>>c;rep(i,1,n){ll d,x;cin>>d>>x;if(d<=k) continue;a[++cnt].d=d;a[cnt].x=x;a[cnt].f=a[cnt].d/k*a[cnt].x;}sort(a+1,a+1+cnt,cmp);ll ans=0;for(int i=1;i<=cnt;++i){ll d=a[i].d;ll x=a[i].x;ll tmp=(ll)ceil(1.0*(d-k)/k);//printf("tmp:%lld\n",tmp);if(c>=tmp){c-=tmp;continue;}else{ans+=(tmp-c)*x;c=0;}printf("ans:%lld\n",ans);}cout<<ans<<endl;
}

E. 只有一端开口的瓶子

题意，给你一个序列，问你需要几个栈能实现 将这个序列从小到大排序。

栈的操作有三类：

1. 取出序列当前的第一个数字，插入到第 pp 个栈的顶部：push p
2. 取出第 pp 个栈的顶部数字，插入到新序列的末尾位置：pop p
3. 取出第 pp 个栈的顶部数字，插入到第 qq 个栈的顶部：move p q

通过简单的观察可以发现，我们最多只需要两个栈就可以实现排序了。

最少需要一个栈。

我们先用一个栈看能不能实现排序，若能输出1，若不能输出2就可以了。

若只有一个栈进行操作，上面的3种操作就成功的减少至 以下两种了：

1. 取出序列当前的第一个数字，插入到第 pp 个栈的顶部：push p
2. 取出第 pp 个栈的顶部数字，插入到新序列的末尾位置：pop p

AC代码：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N],newa[N];
int vis[N];
int main(){int n,t;cin>>t;while(t--){cin>>n;rep(i,1,n){cin>>a[i];}int k=0;int mx=0;int cnt=0;stack<int>que;que.push(0x3f3f3f3f);for(int i=1;i<=n;++i){if(a[i]<que.top()) {  //只能将小于栈顶的元素放进这个栈顶 que.push(a[i]);continue;}//若当前数大于当前栈顶元素值，将栈顶元素一一放到新的数组里去就可以了。 while(a[i]>que.top()){newa[++cnt]=que.top();que.pop();}que.push(a[i]);}while(que.size()){ newa[++cnt]=que.top();que.pop();}int ans=1;for(int i=1;i<=cnt;++i){if(newa[i]>newa[i-1]) continue;//是否从小到大排序 else{ans=2;}}printf("%d\n",ans);}
}

F. 风王之瞳

给出n*m的格子，问里面有多少个正方形

2 2 答案  是6

第6个是斜着的。

找规律：如图.excel 画图太麻烦了，直接写草稿纸上了，这个自己画一遍基本就懂了。

 

​
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e2+10;
int main(){int t;cin>>t;ll n,m;while(t--){cin>>n>>m;ll ans=n*m;--n,--m;ll d=2;while(n&&m){ans=ans+1ll*d*n*m;d++;--n,--m;}printf("%lld\n",ans);}
}​

H. 目标是成为数论大师

将公式化简以下发现是一个一元二次方程。注意 原方程是含根号的： sqrt（a*x）。也就是说你求得根要满足原方程的定义域。a*x>=0，但是这样处理还 是不能A。我想了一会，决定将求出的答案代入原方程是否相等，就A了

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;const int N=1e2+10;
int main(){int t;cin>>t;int x,y;while(t--){cin>>x>>y;int b=-(2*y+x);int c=y*y;int k=b*b-4*c;if(k==0){printf("1\n");printf("%d\n",-b/2);continue;}int tmp=(int)sqrt(1.0*k);int ans1=(-b+tmp)/2,ans2=(-b-tmp)/2;vector<int>ans;if(ans1*x>=0){if((int)sqrt(1.0*x*ans1)+y==ans1)ans.pb(ans1);}if(ans2*x>=0) {if((int)(sqrt(1.0*x*ans2)+y==ans2))ans.pb(ans2);}sort(ans.begin(),ans.end());printf("%d\n",ans.size());for(int i=0;i<ans.size();++i) {printf("%d ",ans[i]);}puts("");}return 0;
}

 

J. 金色传说

题意： n位，每位上可以放0~9，和+  -。问所有合法的放法的运算和是多少。

我的理解：设dp[i]位后i位的合法种类数。从i=3开始，因为最后一位不能为操作符。。
则转移方程就是dp[i]=dp[i-1]*10+dp[i-2]*20...

前i-1位合法种类数在第i位放数字有10种放法。

前i-2位合法种类数在第i位放数字，第i-1位放操作符，有是二十种放法

 

设ans[i]为前i位只放数字时的所有合法数字之和。这里可以用等差数列求，也可以用许老师讲的：ans[i]=ans[i-1]*10+45*pow(i-1);

这dp太秒了呀

 

/*¼ò»¯°æ*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int N=5e5+10; 
const ll mod=998244353  ;
ll n,k;
ll dp[N],ans[N];
ll powmod(ll a,ll b){ll res=1;a%=mod;for(; b;b>>=1){if(b&1) res=res*a%mod;a=a*a%mod;}return res%mod;
}
int main(){int t;ans[1]=45;ans[2]=4950;dp[1]=10;dp[2]=100;for(int i=3;i<N;++i){dp[i]=(10*dp[i-1]+20*dp[i-2])%mod;ll tmp=powmod(10,i);ans[i]=(tmp*(tmp-1)/2)%mod;}cin>>t;while(t--){int n;cin>>n;ll res=ans[n];for(int i=2;i<=n-1;++i){res=(res+2ll*ans[i-1]*dp[n-i]%mod)%mod;	}printf("%lld\n",res%mod);}
}

 

K. 多项式求导

我wa了三发，是没看清a[i]的范围可以为零。。。。。所以啊，读题要读清

K题由于数据比较小，暴力就可以了。每次将幂次方减一，若幂次方为-1了，这个系数就是零了

注意取模

AC代码：

 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e2+10;
const ll mod=998244353 ;
ll n,k;
ll a[N];
vector<ll>ans1,ans2;
ll cal(ll n,ll k){if(k>n) return 0;ll res=1;while(k--){res=res*n%mod;n--;}return res%mod;
}
int main(){cin>>n>>k;rep(i,1,n+1) cin>>a[i];ll d=n;for(int i=1;i<=n-k+1;++i){ll x=cal(d,k)*a[i]%mod;d--;ans2.pb(x);}//ans1.pb(0);while(k--) ans1.pb(0);for(int i=0;i<ans1.size();++i) printf("%lld ",ans1[i]);for(int i=0;i<ans2.size();++i) printf("%lld ",ans2[i]);
}

 

L. 旅行的意义

time limit per test

1.0 s

memory limit per test

256 MB

input

standard input

output

standard output

为什么有人永远渴望旅行，或许就因为，巧合和温暖会在下一秒蜂拥而至吧。

一直想去旅游的天天决定在即将到来的五一假期中安排一场环游世界的旅行。为此，他已经提前查阅了很多资料，并准备画一张旅游路线图。天天先将所有可能会去的 nn 个旅游城市依次编号标记为 1,2,⋯,n1,2,⋯,n。如果从城市 AA 到城市 BB 有一条直达的铁路线路，他就会在图上画上一条从 AA 向 BB 的有向线段。因为天天不喜欢把时间浪费在往返的乘车上，因此他设计的旅游地图路线是一个有向无环图。

天天身在 11 号城市，他每到达一个旅游城市都会先花一天的时间游玩当地的旅游景点。接下来他也没有明确的目的地，所以第二天他会随机地选择该城市的一条直达线路，花费一天的时间通往下一个旅游城市。当然，如果这个城市的旅游景点太好玩的话，他可能会选择再逗留一天，但是由于假期有限，他在当前的旅游城市最多只能呆 22 天。例如，当天天在城市 CC 时，若城市 CC 有 22 条直达线路分别通往城市 AA 和城市 BB，则在第一天的游玩过后，第二天他有 1313 的可能会选择继续逗留在城市 CC 多游玩一天，但是第三天他一定不会再逗留在城市 CC 了；同时他有 1313 可能会选择立即搭乘直达城市 AA 的高铁；他也有 1313 的可能会选择立即搭乘直达城市 BB 的高铁。

当天天把所有的旅游城市都游玩过后，他也就只能结束这段难忘的五一旅行假期了。现在请聪明的你帮天天提前计算一下，他本次旅行时间的期望是多少呢？

容易证明天天旅行时间的期望为 PQPQ 的形式，其中 PP 和 QQ 互质，且 Q≢0 (mod 998244353)Q≢0 (mod 998244353)。因此答案请以 P⋅Q−1 (mod 998244353)P⋅Q−1 (mod 998244353) 的形式输出，其中 Q−1Q−1 表示 QQ 在取模 998244353998244353 下的逆元。

Input

第一行输入一个正整数 T (1≤T≤10)T (1≤T≤10)，表示数据组数。接下来 TT 组数据，每组数据均满足：

• 第一行输入两个非负整数 n (1≤n≤105)n (1≤n≤105) 和 m (0≤m≤105)m (0≤m≤105)，分别表示天天可能旅行的城市数量 nn 和它们之间的直达线路数量 mm。
• 接下来 mm 行，每行输入两个正整数 uu 和 v (1≤u,v≤n)v (1≤u,v≤n)，表示从城市 uu 到 vv 有一条单向直达线路，保证两个旅游城市之间最多只有 11 条直达线路。

Output

对于每组数据，请输出一个非负整数，表示天天旅行时间的期望，注意换行。

Example

input

Copy

2
1 0
2 1
1 2

output

Copy

2
499122181

Note

第一组样例只有一个旅游城市。首先，天天会在该城市游玩一天，第二天只剩下一个选择——留下来接着玩一天，再之后他就只能结束旅程了，所以旅游时间的期望是 22。

第二组样例由两个旅游城市，从城市 11 到城市 22 有一条直达的线路。天天首先在城市 11 游玩一天，然后有 1212 的概率前往城市 22，这将花费 11 天时间乘坐高铁；当然天天也有 1212 的概率逗留在城市 11 多玩一天，第三天再乘坐高铁前往城市 22。因此刚到达城市 22 时，天天花费的旅行时间期望是 1+[12⋅1+12⋅(1+1)]=2.51+[12⋅1+12⋅(1+1)]=2.5 天。接着天天会在城市 22 先游玩一天，但是接下来他没有其他城市可以去了，只能选择继续逗留一天然后终止旅程，容易算出本次旅程总的时间期望为 4.54.5 天，即 92=9⋅2−1 (mod 998244353)=49912218192=9⋅2−1 (mod 998244353)=499122181。

抓住重点：每次到达一个城市一定是先玩一天，第二天有几率再玩一天，第三天必须得走。走向下一个城市得时候会发费一天得时间坐高铁。

设dp[u]代表着从u结点出发时的游玩天数的期望。部分题解写在代码里了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=1e5+10;
vector<int>G[N];//存图 
ll dp[N];
ll powmod(ll a,ll b){ll res=1;a%=mod;for(; b;b>>=1){if(b&1) res=res*a%mod;a=a*a%mod;}return res%mod;
}ll inv(ll x){return powmod(x,mod-2);
}
void dfs(int u){ll len=G[u].size();if(u==1) dp[1]=1+inv(len+1);//从一城市开始，必先玩一天1//第二天有1/(len+1)的概率再玩一天：：1+1/(len+1)  else  dp[u]=2+inv(len+1);//坐高铁花一天和到达一个城市先玩一天，//第二天有1/(len+1)的概率再玩一天 for(auto v:G[u]){if(dp[v]){dp[u]=(dp[u]+dp[v]*inv(len)%mod)%mod;//有1/(len)的概率去这个儿子结点 }else{dfs(v);dp[u]=(dp[u]+dp[v]*inv(len)%mod)%mod;}} 
}
int main(){int t;cin>>t;while(t--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) G[i].clear(),dp[i]=0;for(int i=1;i<=m;++i){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);}dfs(1);printf("%lld\n",dp[1]%mod);}
}