http://acm.hdu.edu.cn/search.php?field=problem&key=642ccpcQHD&source=1&searchmode=source
6734 签到:
include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
while(n%2 == 0) n /= 2;
while(n%5 == 0) n /= 5;
if(n == 1) cout << "No\n";
else cout << "Yes\n";
}
}
6735 网络流建图
include<bits/stdc++.h>
#define ll long long
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(int ii=b;ii>=a;--ii)
#define forn(i,x,g,e) for(int i=g[x];i;i=e[i].next)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ull unsigned long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
#define show(x) cout<<#x<<"="<<x<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show5(v,w,x,y,z) cout<<#v<<"="<<v<<" "<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa2(x,a,b) cout<<#x<<": ";rep(i,a,b) cout<<x[i]<<' ';cout<<endl
using namespace std;//head
const int maxn=2e4+10,maxm=1e5+10;
const ll INF=0x3f3f3f3f,mod=1e9+7;
int casn,n,m,k;
template<typename T>
class mxf{public:
struct node{int to,next;T cap;}e[maxm<<1];
int cur[maxn],head[maxn],que[maxn],dis[maxn],nume=1,s,t;
inline void adde(int a,int b,T c){
e[++nume]={b,head[a],c};head[a]=nume;
}
inline void add(int a,int b,int c){adde(a,b,c);adde(b,a,0);}
void init(int n=maxn-1){memset(head,0,(n+1)<<2);nume=1;}
bool bfs(){
memset(dis,-1,(t+1)<<2);
dis[t]=0,que[0]=t;
int tp=0,ed=1;
while(tp!=ed){
int now=que[tp++];tp%=maxn;
for(int i=head[now];i;i=e[i].next){
int to=e[i].to;
if(dis[to]==-1&&e[i^1].cap){
dis[to]=dis[now]+1;
if(to==s) return true;
que[ed++]=to;ed%=maxn;
}
}
}
return false;
}
T dfs(int now,T flow=0x3f3f3f3f){
if(now==t||flow==0) return flow;
T use=0;
for(int &i=head[now];i&&use!=flow;i=e[i].next){
int to=e[i].to;
if(dis[to]+1!=dis[now])continue;
T tmp=dfs(to,min(e[i].cap,flow-use));
e[i].cap-=tmp,e[i^1].cap+=tmp,use+=tmp;
}
if(!use) dis[now]=-1;
return use;
}
T getflow(int ss,int tt){
s=ss,t=tt;T ans=0;
memcpy(cur,head,(t+1)<<2);
while(bfs()){
ans+=dfs(s);
memcpy(head,cur,(t+1)<<2);
}
return ans;
}
};
mxf<int> net;
int a,b;
char pz[200][200];
int p[200],t[200];
int main() {IO;
cin>>casn;
while(casn--){
cin>>n>>m>>a>>b;
// n=m=a=b=100;
rep(i,0,n+1)rep(j,1,m+1){
pz[i][j]=0;
}
rep(i,1,n) cin>>pz[i]+1;
rep(i,1,a) cin>>p[i];
rep(i,1,b) cin>>t[i];
// rep(i,1,n) cin>>pz[i]+1;
// rep(i,1,a) cin>>p[i];
// rep(i,1,b) cin>>t[i];
int tot=n*m*2+2*m+5;
net.init(tot);
int ss=tot-2,tt=tot-1;
rep(i,1,a) {
net.add(ss,n*m*2+p[i],1);
net.add(n*m*2+p[i],p[i],1);
}
rep(i,1,b){
net.add((n-1)*m+t[i],n*m*2+m+t[i],1);
net.add(n*m*2+m+t[i],tt,1);
}
rep(i,1,n)rep(j,1,m){
if(pz[i][j]!='0') continue;
int id1=(i-1)*m+j;
int id2=n*m+id1;
if(pz[i+1][j]=='0'){
net.add(id1,id1+m,1);
}
if(pz[i][j+1]=='0'){
net.add(id2,id2+1,1);
net.add(id2+1,id2,1);
}
net.add(id1,id2,1);
net.add(id2,id1,1);
}
int ans=net.getflow(ss,tt);
if(ans==a) cout<<"Yes\n";
else cout<<"No\n";
}
}
6731 几何+手写hashmap
include<bits/stdc++.h>
#define ull unsigned long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define for1(I, A, B) for (int I = (A); I < (B); ++I)
#define forn(I, A, B) for (int I = (A); I <= (B); ++I)
#define Mod(a,b) a<b?a:a%b+b
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define show(x) cout<<#x<<"="<<x<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show5(v,w,x,y,z) cout<<#v<<"="<<v<<" "<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showmm(x,a,b) rep(i,0,a) rep(j,0,b) cout<<#x<<'['<<i<<']'<<'['<<j<<"]="<<x[i][j]<<(" \n"[j==b])
#define showm(x,a,b) rep(i,0,a) rep(j,0,b) cout<<x[i][j]<<(" \n"[j==b])
#define showa1(x,a,b) cout<<#x<<":\n";rep(i,a,b) showa(x,i);cout<<endl
#define showa2(x,a,b) cout<<#x<<": ";rep(i,a,b) cout<<x[i]<<' ';cout<<endl
using namespace std;
typedef int ll;
typedef vector<int> vi;
typedef set<int> si;
typedef double db;
const db eps=1e-8;
const db pi=acos(-1);
const ll inf=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int MAX=4e3+10;
const ll mod=1e9+7;
ll ans[MAX];
#define fi first
#define se second
const int maxsz=4e6+9;
template<typename key,typename val>
class hash_map{public:
struct node{key u;val v;int next;};
vector<node> e;
int head[maxsz],nume,numk,id[maxsz];
int geths(pair<int,int> &u){
int x=(1ll*u.fi*mod+u.se)%maxsz;
if(x<0) return x+maxsz;
return x;
}
val& operator[](key u){
int hs=geths(u);
for(int i=head[hs];i;i=e[i].next)if(e[i].u==u) return e[i].v;
if(!head[hs])id[++numk]=hs;
if(++nume>=e.size())e.resize(nume<<1);
return e[nume]=(node){u,0,head[hs]},head[hs]=nume,e[nume].v;
}
void clear(){
rep(i,0,numk)head[id[i]]=0;
numk=nume=0;
}
};
hash_map<pair<int,int>,int> mp,mpn,mpq;
struct point{int x,y;}p[MAX],q[MAX];
int main(){IO;
int n,Q;
while(cin>>n>>Q){
forn(i,1,Q)ans[i]=0;
forn(i,1,n)cin>>p[i].x>>p[i].y;
forn(i,1,Q)cin>>q[i].x>>q[i].y;
forn(i,1,Q){
mp.clear();
forn(j,1,n){
int X=p[j].x;
int Y=p[j].y;
X-=q[i].x;
Y-=q[i].y;
int g=__gcd(abs(X),abs(Y));
if(g!=0)X/=g,Y/=g;
mp[make_pair(X,Y)]++;
}
forn(j,1,n){
int X=p[j].x;
int Y=p[j].y;
X-=q[i].x;
Y-=q[i].y;
int g=__gcd(abs(X),abs(Y));
if(g!=0)X/=g,Y/=g;
ans[i]+=mp[make_pair(Y,-X)];
}
}
forn(i,1,n){
mpn.clear();
mpq.clear();
forn(j,1,n){
ll X=p[j].x;
ll Y=p[j].y;
X-=p[i].x;
Y-=p[i].y;
ll g=__gcd(abs(X),abs(Y));
if(g!=0) X/=g,Y/=g;
mpn[make_pair(X,Y)]++;
}
forn(j,1,Q){
ll X=q[j].x;
ll Y=q[j].y;
X-=p[i].x;
Y-=p[i].y;
ll g=__gcd(abs(X),abs(Y));
if(g!=0) X/=g,Y/=g;
mpq[make_pair(X,Y)]++;
}
forn(j,1,Q){
ll tx=q[j].x-p[i].x;
ll ty=q[j].y-p[i].y;
ll g=__gcd(abs(tx),abs(ty));
if(g!=0)tx/=g,ty/=g;
ans[j]+=mpn[make_pair(ty,-tx)]+mpn[make_pair(-ty,tx)];
}
}
forn(i,1,Q)cout<<ans[i]<<endl;
}
}
6739 DP,6*6*n
include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+10;
int dp[maxn][6];
string ss[26][6];
string F(string s, int k) {
if(k == 0) return s;
string ans = "";
if(k == 1) {
ans += s[0];
ans += s[2];
ans += s[1];
return ans;
}
if(k == 2) {
ans += s[1];
ans += s[0];
ans += s[2];
return ans;
}
if(k == 3) {
ans += s[1];
ans += s[2];
ans += s[0];
return ans;
}
if(k == 4) {
ans += s[2];
ans += s[0];
ans += s[1];
return ans;
}
if(k == 5) {
ans += s[2];
ans += s[1];
ans += s[0];
return ans;
}
}
void init() {
for(int i = 0; i < 26; i++)
ss[i][0] = "KKK";
ss['Y'-'A'][0] = "QQQ";
ss['V'-'A'][0] = "QQW";
ss['G'-'A'][0] = "QQE";
ss['C'-'A'][0] = "WWW";
ss['X'-'A'][0] = "QWW";
ss['Z'-'A'][0] = "WWE";
ss['T'-'A'][0] = "EEE";
ss['F'-'A'][0] = "QEE";
ss['D'-'A'][0] = "WEE";
ss['B'-'A'][0] = "QWE";
for(int i = 0; i < 26; i++)
for(int j = 1; j < 6; j++) {
ss[i][j] = F(ss[i][0], j);
}
}
int CNT(string s1, string s2) {
if(s1 == s2) return 0;
if(s1[1] == s2[0] && s1[2] == s2[1]) return 1;
if(s1[2] == s2[0]) return 2;
return 3;
}
int main() {
std::ios::sync_with_stdio(false);
init();
string s;
while(cin >> s) {
s = " "+s;
for(int i = 0; i < s.length(); i++)
for(int j = 0; j < 6; j++)
dp[i][j] = 1e9;
for(int i = 0; i < 6; i++)
dp[1][i] = 3;
for(int i = 2; i < s.length(); i++) {
for(int j = 0; j < 6; j++) {
for(int k = 0; k < 6; k++) {
dp[i][k] = min(dp[i][k], dp[i-1][j]+CNT(ss[s[i-1]-'A'][j], ss[s[i]-'A'][k]));
}
}
}
int mi = 1e9;
for(int i = 0; i < 6; i++)
mi = min(mi, dp[s.length()-1][i]);
cout << mi+s.length()-1 << "\n";
}
}
6740 水kmp
include<bits/stdc++.h>
#define ll long long
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(int ii=b;ii>=a;--ii)
#define forn(i,x,g,e) for(int i=g[x];i;i=e[i].next)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ull unsigned long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
using namespace std;//head
const int maxn=1e7+10,maxm=2e6+10;
const ll INF=0x3f3f3f3f,mod=1e9+7;
int casn,n,m,k;
class prefix{public:
int p[maxn],lens;
char *s;
void init(char *_s,int _lens){
s=_s,lens=_lens;
rep(i,0,lens-1) p[i]=0;
p[0]=-1;
int now=0,pos=-1;
while(now<lens)
if(pos==-1||s[now]==s[pos]) p[++now]=++pos;
else pos=p[pos];
}
vector<int> find(char *t,int lent){
int now,pos=0;
vector<int> ans;
while(now<lent) {
if(pos==-1||t[now]==s[pos]) pos++,now++;
else pos=p[pos];
if(pos==lens) pos=p[pos],ans.push_back(now-lens);
}
return ans;
}
}kmp;
ll a,b;
char s[maxn];
int main() {IO;
while(cin>>a>>b){
cin>>s;
int len=strlen(s);
reverse(s,s+len);
while(s[len-1]!='.') len--;
len--;
s[len]=0;
kmp.init(s,len);
ll ans=a*len-b*len;
rep(i,1,len){
int l=i-kmp.p[i];
ans=max(ans,(a*(i)-b*l));
}
cout<<ans<<endl;
}
}