hihocoder编程练习赛54
A
描述
给定一个真分数P/Q(P < Q)，请你求出它的小数部分都包括0~9中的哪些数字。
例如1/2=0.5，只包含数字5；1/3=0.33333……，只包含数字3，1/7=0.142857142857……，包含数字124578。
输入
两个整数P和Q，1 ≤ P < Q ≤ 1000000
输出
从小到大输出小数部分出现的所有数字
样例输入
13 123
样例输出
01569
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| using namespace std; int p,q; int vis[15]; int main(){ // freopen("input.txt","r",stdin); while(cin>>p>>q){ int num=0; memset(vis,0,sizeof vis); while(1){ if(num==10000) break; if(p<q) p*=10; vis[p/q]=1; p%=q; if(p==0) break; num++; } for(int i=0;i<=9;i++){ if(vis[i]) cout<<i; } cout<<endl; } return 0; }
|
思路
模拟除的过程
B
描述
愚人节那天，小Ho在小Hi的一个回文字符串中添加了一个字符。你能帮助小Hi找到被添加的是第几个字符吗？
输入
一个只包含小写字母的字符串S。
对于70%的数据，|S| ≤ 1000
对于100%的数据，|S| ≤ 500000
输出
输出一个整数K，表示删除第K(从1开始计数)个字符后，S会变成一个回文字符串。
数据保证有解。如果有多个解，输出其中K最小的。
样例输入
aaba
样例输出
1
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| using namespace std; int l[maxn],len; char s[maxn],tmp[maxn]; bool check(int x){ int cnt=0; for(int i=1;i<=len;i++){ if(i==x) continue; tmp[++cnt]=s[i]; } for(int i=1;i<=cnt/2;i++){ if(tmp[i]!=tmp[cnt-i+1]) return false; } return true; } int main(){ scanf("%s",s+1); len=strlen(s+1); memset(l,0,sizeof l); l[1]=1; for(int i=2;i<=len;i++){ if(s[i]==s[i-1]) l[i]=l[i-1]; else l[i]=i; } int ans=0; for(int i=1;i<=len/2;i++){ if(s[i]==s[len-i+1]) continue; if(check(i)){ ans=i; break; } if(check(len-i+1)){ ans=len-i+1; break; } } if(ans==0) ans=len/2+1; cout<<l[ans]<<endl; return 0; }
|
思路
n方check
l存放每个连续数字出现的最左边位置
然后遍历i到len/2的位置 判断删除i和删除len-i+1是否能构成回文串
可以的话输出l[pos]
注意如果没有找到这样的pos 说明pos=len/2+1 也就是中间的位置
C
描述
给定N个数组，每个数组都包含M个整数。
现在你被要求从每个数组中选出一个数，总共N个数，然后求出其中最大与最小的差值。
在MN种选法中，差值最小是多少？
输入
第一行包含两个整数N和M。
以下N行，每行包含M个整数。
对于50%的数据，1 ≤ N × M ≤ 10000
对于100%的数据，1 ≤ N × M ≤ 200000 0 ≤ 每个整数 ≤ 1000000
输出
最小的差值
样例输入
3 3
8 1 6
3 5 7
4 9 2
样例输出
2
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| using namespace std; vector<pii>v; int n,m; int cnt[maxn]; int main(){ // freopen("input.txt","r",stdin); cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int x; cin>>x; v.push_back(make_pair(x,i)); } } sort(v.begin(),v.end()); int num=0,ed=0; int ans=inf; for(int st=0;st<v.size();st++){ while(ed<v.size() && num<n){ cnt[v[ed].second]++; if(cnt[v[ed].second]==1) num++; ed++; } if(num==n) ans=min(ans,v[ed-1].first-v[st].first); cnt[v[st].second]--; if(cnt[v[st].second]==0) num--; } cout<<ans<<endl; return 0; }
|
思路
把n×m的数字放到一个vector里 排序后尺取
每次保证一个窗口里有n个不同行的数字
