昨天的个人训练赛。比较水的题,但是我没作出几个来。暴露出很多问题。
比赛地址。居然是被禁用的url?
A题。最水的。题目有点难懂,最后抱着试一试的态度给过了。
B题。字符串。给一些文件的路径和扩展名,要询问某个路径中后缀名是XX的文件。暴力枚举。。
比赛的时候纠结于string类的substr怎么整。substr(a,b)表示从string t中抽取从a开始的b个字符到另一个string中。
还有这个题可以用java的startwith和endwith。。愣是想不到。想不到是硬伤。
C题。给一个矩阵A,求最大的子矩阵(是正方形H*H)满足元素和不大于limit。
用二分(还是想不到),二分H,然后枚举所有符合条件的H,利用子矩阵和可以简单实现。
ma[i][j]=ma[i][j-1]+ma[i-1][j]-ma[i-1][j-1]+d;跟二维的树状数组是一样的。。
D题。给一棵家族树,然后询问两个人的关系,是直系祖父母还是其他的亲戚关系。对于每一个询问,如果能从a dfs到b,那么a就是b的子孙,如果能从b dfs到a,那么b就是a的子孙,否则他两就是relatives。
dfs的时候用回溯法记录找寻过的关系,父亲是m,母亲是f。然后输出那个数组里面的就ok。
E题。给一个数组,问数组里面满足a[i]+a[j]==x(i<j)的数据对数。可以用hash搞,但是我不会。
我用的二分,先是wa,然后tle,然后函数限制,然后又wa。。跪了。
之前见过这个题,但是就是想不起来怎么搞了。只是记得当时的方法想老半天也想不出来,也挺巧的,还怀疑过它的正确性。
弄两个指针,对排序后的数组从左往右和从右往左扫描,如果加起来和大于limit,右边减一,如果小于,左边加一。
#include<cstring> #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> using namespace std; #define ll long long ll a[100010]; int main(){ int n; ll m; while(~scanf("%d%I64d",&n,&m)){ for(int i=0;i<n;i++) scanf("%I64d",&a[i]); int l=0,r=n-1; ll cnt=0; sort(a,a+n); while(l<r){ while(a[l]+a[r]<m&&l<r)l++; while(a[r]+a[l]>m&&l<r)r--; if(a[l]+a[r]==m){ int tmp1=1,tmp2=1; while(a[l]==a[l+1]&&l+1<n)l++,tmp1++; while(a[r]==a[r-1]&&r>0)r--,tmp2++; if(a[l]==a[r])cnt+=(ll)(tmp1)*(tmp1-1)/2; else cnt+=(ll)tmp1*tmp2; l++,r--; } } printf("%I64d\n",cnt); } return 0; }
F题,不会。据说是并查集。
G题。dp,不会。
H题。I题。两个类似。找规律,一个是公比为3的一个是公比为2的。没了。
好好练吧,被队友超过很不爽啊。