Fluctuation Limit
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6860
这题刚开始我的思路是正确的,当时是想根据题目的限制条件推出每一天的可能范围,但后面在代码实现时不知道哪里想错了,就认为这个方法不可行。后面尝试dfs,预计会超时,稍稍试了一下剪枝之后还是不行,后面只好放弃了。
首先每一天要取股票可能的价格区间和预测价格的区间最小值;比如第i-1天股票价格可能为 [l,r] , 预测价格为 [L,R] 。那么第i天的股票价格范围就是:[ min(l-k,L) , min(r+k,R) ];根据这种递推关系,依次求出每一天的价格区间即可;输出价格的时候,可以从最后一天开始计算,依次取区间最大值,如果第i天取res,如果第i-1天的右端点>=res+k,那么第i-1天就取res+k,否则就取第i-1天的右端点即可;
#include<iostream> #include<vector> using namespace std; const int N = 1e5+10; int l[N],r[N]; int n,k; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d%d",&l[i],&r[i]); } vector<int> ve; bool flag=0; for(int i=2;i<=n;i++){ l[i]=max(l[i],l[i-1]-k); r[i]=min(r[i],r[i-1]+k); if(l[i]>r[i]){ flag=1; break; } } if(flag){ printf("NO\n"); continue ; } ve.push_back(l[n]); int la=l[n]-k,ra=l[n]+k; for(int i=n-1;i>=1;i--){ l[i]=max(la,l[i]); r[i]=min(ra,r[i]); ve.push_back(l[i]); la=l[i]-k; ra=l[i]+k; } int len=ve.size(); printf("YES\n"); for(int i=len-1;i>=0;i--){ printf("%d ",ve[i]); } puts(""); } return 0; }
Isomorphic Strings
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6863
这题如果hash用的比较熟的话,还是挺好做的。奈何我hash会点皮毛,而且当时想了两个角度,然后果断选了KMP/(ㄒoㄒ)/~~,毕竟KMP看了比较多。本身我的思维漏洞也挺多的,后面一一修正过来之后,还是T到怀疑人生。之前看好多人的代码时间差非常大,还有一点信心,但我的死活过不了。。。还是老老实实学好hash吧。
#include <algorithm> #include <iostream> #include <map> #include<cstring> #define ll long long using namespace std; const ll mod = 13331; const double eps = 1e-6; const ll inf = 0x3f3f3f3f; const ll N = 5e6 + 10; ll num[30],ha[N],p[N]; char s[N]; map<ll,ll> mp; int main(){ p[0]=1; for(ll i=1;i<N;i++) p[i]=p[i-1]*mod; ll t; scanf("%lld",&t); while(t--){ ll n; scanf("%lld",&n); scanf("%s",s+1); memset(num,0,sizeof(num)); ha[0] = 0; for(ll i=1;i<=n;i++){ num[s[i]-'a'+1]++; ha[i]=ha[i-1]*mod+(s[i]-'a'+1); } ll gg=n; for(ll i=1;i<=26;i++){ if(num[i]) gg=__gcd(gg,num[i]); } ll u=n/gg; ll flag=1; if(u==1&&n!=1) flag=0; else{ for(ll i=1;i<gg;i++){ ll len=i*u; if(n%len) continue; flag= 0; mp.clear(); LL k=ha[len]-ha[0]*p[len]; mp[k]=1; for(ll j=1;j<len;j++){ k=k*mod+(s[j]-96); mp[k-ha[j]*p[len]]=1; } for(ll j=1;j*len<=n;j++){ if (mp[ha[j*len]-ha[(j-1)*len]*p[len]]==0){ flag=1; break; } } if(flag==0) break; } } if(flag==0) printf("Yes\n"); else printf("No\n"); } return 0; }