HDU5211
思路：
倒着更新每个数的约数，更新完要把自己加上，以及1的情况？
//#include <bits/stdc++.h>
#include<iostream>
#include<map>
#include<cstdio>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
//找最近倍数
const int N=1e4+10; map<int,int>mp;
void solve(int n,int id)
{
int q=sqrt(n);
if(n==1)
return;
mp[1]=id;
for(int i=2;i<=q;++i)
if(n%i==0)
{
mp[i]=id;
mp[n/i]=id;
}
}
int x[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
int ans=0;
mp.clear();
for(int i=1;i<=n;i++)
scanf("%d",&x[i]);
for(int i=n;i>=1;i--)
{
solve(x[i],i);
ans+=mp[x[i]];
mp[x[i]]=i;
}
printf("%d\n",ans);
}
return 0;
}
HDU5228
注意本身牌可随意变换顺序= =、
//#include <bits/stdc++.h>
#include<iostream>
#include<map>
#include<cstdio>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
char str[5];
int a[5][13];
int b[5][13];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof(a));
for(int i=0; i<5; i++)
{
scanf("%s",str);
int len=strlen(str);
if(len==3)
a[str[0]-'A'][(str[2]-'0')+(str[1]-'0')*10]=1;
else
a[str[0]-'A'][(str[1]-'0')]=1;
}
int ans=4;
for(int i=0; i<4; i++)
for(int j=1; j<=10; j++)
{
int num=0,k=j;
if(j==10)
{
b[num][0]=i;b[num++][1]=k;k++;
b[num][0]=i;b[num++][1]=k;k++;
b[num][0]=i;b[num++][1]=k;k++;
b[num][0]=i;b[num++][1]=k;k++;
b[num][0]=i;b[num++][1]=1;
}
else
{
b[num][0]=i;b[num++][1]=k;k++;
b[num][0]=i;b[num++][1]=k;k++;
b[num][0]=i;b[num++][1]=k;k++;
b[num][0]=i;b[num++][1]=k;k++;
b[num][0]=i;b[num++][1]=k;
}
int sum=0;
for(k=0; k<5; k++)
if(a[b[k][0]][b[k][1]]==1)
sum++;
ans=min(ans,5-sum);
}
printf("%d\n",ans);
}
return 0;
}
HDU5229
先手赢的话有两种：字符串相同或者字符串两个相加为奇数。
因为字符串相同的话，一定是偶数，所以只要找偶数的相同就好了，也就是说只要找相同就好了
先手赢的贡献=奇数长字符串个数*偶数长字符串个数 + 相同组合数
这里我用的是Trie树处理。
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII; const int N=20000+10; struct Trie{
int num;
Trie *next[26];
};
Trie q[N*10],*root;
int tol,ans,n;
char s[200010]; Trie* Creat()
{
Trie *p=&q[tol++];
for(int i=0;i<26;i++)
p->next[i]=NULL;
p->num=0;
return p;
} int INS()
{
int len=strlen(s);
Trie* p=root;
for(int i=0;i<len;i++)
{
int index=s[i]-'a';
if(p->next[index]==NULL)
p->next[index]=Creat();
p=p->next[index];
}
p->num++;
return p->num;
} int gcd(int x, int y)
{
if (x%y) return gcd(y, x%y);
return y;
} int main()
{
int T;
scanf("%d",&T);
while(T--){
int len,even=0,odd=0;
scanf("%d",&n);
tol=ans=0;
root=Creat();
for(int i=0;i<n;i++)
{
scanf("%s",s);
int temp=INS();
if(temp>2)
{
ans-=(temp-1)*(temp-2)/2;
ans+=(temp-1)*temp/2;
}
else if(temp==2)
ans+=temp*(temp-1)/2;
len=strlen(s);
if(len%2)
odd++;
else
even++;
}
ans+=odd*even;
int pp=ans;
int qq=n*(n-1)/2;
int g=gcd(qq,pp);
if(pp==0)
puts("0/1");
else
printf("%d/%d\n",pp/g,qq/g);
}
return 0;
}
HDU5232
水题；
//#include <bits/stdc++.h>
#include<iostream>
#include<map>
#include<cstdio>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1e6+10; int a[105][105],ans;
int main()
{
int n;
while (scanf("%d",&n)!=EOF)
{
ans=n*2;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++)
if (a[i][j]) ans+=2;
printf("%d\n",ans);
}
}
HDU5233
思路：
这道题可以二分，也能用map嵌套一个queue（很有可能mle），这里给出一个好的思想：预留；
对鸟每个位置的高度加一个预留位置，从最后往前枚举预处理一下，然后每次取完更新位置。
//#include <bits/stdc++.h>
#include<iostream>
#include<map>
#include<cstdio>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1e6+10; struct asd{
int id;
int next;
};
asd q[N];
map<int,int>mp;
int a[N],m,n,num; int main()
{
while(~scanf("%d%d",&n,&m)){
mp.clear();
num=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n;i>=1;i--)
{
q[++num].id=i;
q[num].next=mp[a[i]];
mp[a[i]]=num;
}
for(int i=1;i<=m;i++){
int x,temp;
scanf("%d",&x);
temp=mp[x];
if(!temp)
puts("-1");
else
printf("%d\n",q[temp].id);
mp[x]=q[temp].next;
}
}
return 0;
}