字符串哈希
P4503 [CTSC2014]企鹅QQ
题意:给定n个互不相同的串,求两两之间只有一位不同的字符串对有多少个。
思路:
复杂度在:n2 *L
4.5e11,不能接受。
发现时间消耗主要在两个串的逐位比较上,考虑单哈希优化。
采用进制哈希,对比两串时逐位删去对应进制的哈希值,如果两串此时哈希值相等,由于题目说不含有相同的字符串,所以这一对一定就是合法的一对字符串。
考虑在对比两个哈希值之前现行排序
最后可以优化到nL+nlogn+n,在接受范围之内
#include
#define ll long long
using namespace std;
int n,l,s;
ll ha[30005],t[30005],Hina[205];
char c[300005][205];
const int p = 2333;
int main()
{
cin>>n>>l>>s;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=l;j++)
{
cin>>c[i][j];
ha[i]=ha[i]*p+c[i][j];
}
}
Hina[0]=1;
for(int i=1;i<=l;i++)
{
Hina[i]=Hina[i-1]*p;
}
int ans=0;
for(int i=1;i<=l;i++)
{
for(int j=1;j<=n;j++)
{
t[j]=ha[j]-c[j][i]*Hina[l-i];
}
sort(t+1,t+n+1);
int tmp=1;
for(int j=1;j<n;j++)
{
if(t[j]!=t[j+1])
tmp=1;
else
{
ans+=tmp;
tmp++;
}
}
}
printf("%d\n",ans);
return 0;
}
题意:将原数组A构造为环形波动数组
思路:环形波动数组简化了问题,可见奇数有至少(n+1)/2个波峰/波谷的情况下是不符合题目要求的。
再看偶数情况下如果有num个相同的x,那么就必须有对应的至少num个数大于/小于x
以上就是无法构造的情况。
可以构造时,按照贪心策略,最小的和中间大的((n+1)/2+1)交替输出即可(或许你可以搞两个堆,但是没必要)
#include
#include
#define endl '\n'
using namespace std;
const int N = 1e5+100;
int a[N];
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t;
for(cin>>t;t;t--)
{
int n,cnt=1;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
bool falg=true;
for(int i=1;i<n;i++)
{
if(n-i<cnt&&cnt>i-cnt)
{
falg=false;
break;
}
if(a[i]==a[i+1])
cnt++;
else
cnt=1;
}
if(falg&&!(n&1))
{
cout<<"YES"<<endl;
for(int i=1,j=(n+1)/2+1,num=1;num<=n;num++)
{
if(num%2)
cout<<a[i++]<<" ";
else
cout<<a[j++]<<" ";
}
cout<<endl;
}
else
cout<<"NO"<<endl;
}
return 0;
}
好久不打比赛手生了,今天状况频发,四题都没出有点屑了。
Sum
题意:数组里每次拿出两个数加到分数上,然后把这两个数的和再放回去,求最大分数。
思路:排序后,每次让a[i]=a[i]+a[i+1]不就好了。注意求最大值,所以截止到出现负数。
通常是取模1e9+7吧,害,取模1e7+7被背刺了,怨我自己。
#include
#include
using namespace std;
#define int long long
const int mod=1e7+7;
const int N = 2e5+100;
int a[N];
signed main()
{
int t;
for(cin>>t;t;t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
int temp=0,ans=0;
for(int i=n;i>=2;i--)
{
temp=a[i]+a[i-1];
if(temp>0)
ans=ans+temp;
else
break;
a[i-1]=temp;
}
cout<<ans%mod<<endl;
}
return 0;
}
Gaming
题意:每个木板有一定的分数,要求在区间不完全覆盖的情况下获得最大分数。
思路:差分+枚举
先全部都用上,利用差分求出每个点的价值,然后枚举不要那个点失去的分数最少。
#include
#define int long long
using namespace std;
const int N = 1e6+100;
int vis[N],n,m,sum=0,minn=1e16+10;
signed main(){
cin>>n>>m;
for(int i=1,l,r,v;i<=n;i++){
cin>>l>>r>>v;
vis[l]+=v;vis[r+1]-=v;
sum+=v;
}
for(int i=1;i<=m;i++)vis[i]+=vis[i-1];
for(int i=1;i<=m;i++)minn=min(minn,vis[i]);
cout<<sum-minn<<endl;
}
School
题意:在n个区间段不能打电话,然后给定q个时间点,问问你能不能打电话
这题唯一难点的就是n挺大的,所以要二分一下而且要把区间去重。
思路:
我们先将每个时间段的l,r读入然后排序(先r从小到大,r相等则l从小到大)。对于所有r相同的区间只保留l最小的。
对于时间点temp
我们二分出第一个大于等于temp的r的位置,然后从这个位置开始一直往后遍历,直到发现有l小于等于temp则判定为不能打电话。
#include
#include
#define int long long
using namespace std;
const int N = 1e3+100;
int l[N],r[N];
struct node
{
int l,r;
};
node a[N];
bool cmp(const node &a,const node &b)
{
if(a.r==b.r)
return a.l<b.l;
return a.r<b.r;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,h,m,q;
cin>>n>>h>>m>>q;
int cnt=0;
for(int i=1,h1,m1,h2,m2;i<=n;i++)
{
cin>>h1>>m1>>h2>>m2;
a[i].l=h1*m+m1;
a[i].r=h2*m+m2;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(i!=1&&r[i]==r[i-1])
continue;
l[++cnt]=a[i].l;
r[cnt]=a[i].r;
}
for(int i=1,h1,m1;i<=q;i++)
{
cin>>h1>>m1;
int temp=h1*m+m1;
int pos=lower_bound(r+1,r+cnt+1,temp)-r;
if(pos==cnt+1)
{
cout<<"Yes"<<'\n';
}
else
{
bool falg=false;
for(int j=pos;j<=cnt;j++)
{
if(l[j]<=temp)
{
falg=true;
break;
}
}
if(falg)
cout<<"No"<<'\n';
else
cout<<"Yes"<<'\n';
}
}
return 0;
}
Word
给定含有n个字符串的字符串集合,然后给你两个字符串s和t。有改变规则如下
1.每次改变一个字母
2.新生成的字符串必须是集合里有的
问:能否将s变成t?能的话输出最短的操作步数和具体操作方案。
思路:搜索。
#include
using namespace std;
int n,m,x;
string s,t,l;
map <string,bool> mp,vis;
vector <string> T;
struct Node
{
int st;
vector <string> v;
};
queue <Node> q;
void bfs()
{
while(!q.empty())
{
x = q.front().st,T = q.front().v;
q.pop();
for(int i = 0;i < m;i++)
for(int j = 0;j < 26;j++)
{
l = T[x];
l[i] = 'a' + j;
if(l == t)
{
cout << x << endl;
for(int k = 0;k <= x;k++) cout << T[k] << endl;
cout << t << endl;
exit(0);
}
if(vis[l]) continue;
if(!mp.count(l)) continue;
vis[l] = true;
T.push_back(l);
q.push((Node){x + 1,T});
T.pop_back();
}
}
cout << "-1" << endl;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> s;
mp[s] = true;
}
cin >> s >> t;
vector <string> v;
v.push_back(s);
q.push((Node){0,v});
bfs();
return 0;
}