6月26日
被1226烦得头都大了，从下午断断续续调到晚。最后数组开小给报个Tle看了半天没看出来...
6月30日
每日补题，进度停滞中...
7月10日
第一阶段结束...不做鸽子了不做鸽子了。
7月11日
被卡了....还没题解....生命--。
7月21日
达到40题之后已经咸鱼了。随缘做做。
hdu1219
遍历计数。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; char a[];
int cnt[];
int main(){
while(cin.getline(a,)){
memset(cnt,,sizeof(cnt));
int l=strlen(a);
for(int i=;i<l;i++){
cnt[a[i]]++;
}
for(int i='a';i<='z';i++){
printf("%c:%d\n",i,cnt[i]);
}
printf("\n");
}
return QAQ;
}
hdu 1219
hdu1220
总对数减去相邻的对数。相邻的对数分类为 顶点、棱、面、体内 的小正方体，分别对应邻接3、4、5、6个，每对算了两次。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std;
typedef long long ll; ll n; int main(){
while(scanf("%lld",&n)!=EOF){
if(n==){
printf("%lld\n",);
continue;
}
ll sum=n*n*n*(n*n*n-)/,cnt;
cnt=* + *(n-)* + *(n-)*(n-)* + (n-)*(n-)*(n-)*;
printf("%lld\n",sum-cnt/);
}
return QAQ;
}
hdu 1220
hdu1221
最大值一定到在圆心到矩形四个顶点里，最小值除了到顶点距离外，再判一下圆心到四条边距离。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std;
typedef long long ll;
const double eps=1e-; double x,y,r,a1,b1,a2,b2,a3,b3,a4,b4,maxi,mini;
ll T; double dis(double x1, double y1, double x2, double y2){
return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
} int main(){
scanf("%lld",&T);
while(T--){
scanf("%lf%lf%lf%lf%lf%lf%lf",&x,&y,&r,&a1,&b1,&a2,&b2);
a3=a1; b3=b2; a4=a2; b4=b1;
double l1=dis(x,y,a1,b1),l2=dis(x,y,a2,b2),
l3=dis(x,y,a3,b3),l4=dis(x,y,a4,b4); maxi=max( max(l1,l2) , max(l3,l4) );
mini=min( min(l1,l2) , min(l3,l4) ); if(x>a1 && x<a2){
mini=min( mini, min( fabs(y-b1) , fabs(y-b2) ) );
} if(y>b1 && y<b2){
mini=min( mini, min( fabs(x-a1) , fabs(x-a2) ) );
} if(mini<=r && maxi>=r){
printf("YES");
}
else printf("NO");
printf("\n");
}
return QAQ;
}
hdu 1221
hdu1222
如果m和n的最大公约数不为1，则一定有安全位置。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int T,m,n; int gcd(int a,int b){
return b==?a:gcd(b,a%b);
} int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&m,&n);
if(gcd(m,n)!=) printf("YES");
else printf("NO");
printf("\n");
}
return QAQ;
}
hdu 1222
hdu1223
有等号连接的为一个块，dp[i][j]表示i个字母有j个块。对于i-1个字母分两类：1.原有j块，即添加等号，显然和每个块相等为一种，共j种；2.原有j-1块，即添加小于号，j-1个块有j个空位可以放入，也为j种。所以dp[i][j]=dp[i-1][j]*j+dp[i-1]][j-1]*j。
本题没有mod，要用大数。感谢颜神的模板支援o(*￣▽￣*)ブ。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std;
typedef long long ll; int T,n; const int base = ;
const int base_digits = ; struct Bigint {
vector<int> z;
int sign; Bigint() :
sign() {
} Bigint(long long v) {
*this = v;
} Bigint(const string &s) {
read(s);
} void operator=(const Bigint &v) {
sign = v.sign;
z = v.z;
} void operator=(long long v) {
sign = ;
if (v < )
sign = -, v = -v;
z.clear();
for (; v > ; v = v / base)
z.push_back(v % base);
} Bigint operator+(const Bigint &v) const {
if (sign == v.sign) {
Bigint res = v; for (int i = , carry = ; i < (int) max(z.size(), v.z.size()) || carry; ++i) {
if (i == (int) res.z.size())
res.z.push_back();
res.z[i] += carry + (i < (int) z.size() ? z[i] : );
carry = res.z[i] >= base;
if (carry)
res.z[i] -= base;
}
return res;
}
return *this - (-v);
} Bigint operator-(const Bigint &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
Bigint res = *this;
for (int i = , carry = ; i < (int) v.z.size() || carry; ++i) {
res.z[i] -= carry + (i < (int) v.z.size() ? v.z[i] : );
carry = res.z[i] < ;
if (carry)
res.z[i] += base;
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
} void operator*=(int v) {
if (v < )
sign = -sign, v = -v;
for (int i = , carry = ; i < (int) z.size() || carry; ++i) {
if (i == (int) z.size())
z.push_back();
long long cur = z[i] * (long long) v + carry;
carry = (int) (cur / base);
z[i] = (int) (cur % base);
//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
}
trim();
} Bigint operator*(int v) const {
Bigint res = *this;
res *= v;
return res;
} friend pair<Bigint, Bigint> divmod(const Bigint &a1, const Bigint &b1) {
int norm = base / (b1.z.back() + );
Bigint a = a1.abs() * norm;
Bigint b = b1.abs() * norm;
Bigint q, r;
q.z.resize(a.z.size()); for (int i = a.z.size() - ; i >= ; i--) {
r *= base;
r += a.z[i];
int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : ;
int s2 = b.z.size() - < r.z.size() ? r.z[b.z.size() - ] : ;
int d = ((long long) s1 * base + s2) / b.z.back();
r -= b * d;
while (r < )
r += b, --d;
q.z[i] = d;
} q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair(q, r / norm);
} friend Bigint sqrt(const Bigint &a1) {
Bigint a = a1;
while (a.z.empty() || a.z.size() % == )
a.z.push_back(); int n = a.z.size(); int firstDigit = (int) sqrt((double) a.z[n - ] * base + a.z[n - ]);
int norm = base / (firstDigit + );
a *= norm;
a *= norm;
while (a.z.empty() || a.z.size() % == )
a.z.push_back(); Bigint r = (long long) a.z[n - ] * base + a.z[n - ];
firstDigit = (int) sqrt((double) a.z[n - ] * base + a.z[n - ]);
int q = firstDigit;
Bigint res; for(int j = n / - ; j >= ; j--) {
for(; ; --q) {
Bigint r1 = (r - (res * * base + q) * q) * base * base + (j > ? (long long) a.z[ * j - ] * base + a.z[ * j - ] : );
if (r1 >= ) {
r = r1;
break;
}
}
res *= base;
res += q; if (j > ) {
int d1 = res.z.size() + < r.z.size() ? r.z[res.z.size() + ] : ;
int d2 = res.z.size() + < r.z.size() ? r.z[res.z.size() + ] : ;
int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : ;
q = ((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * );
}
} res.trim();
return res / norm;
} Bigint operator/(const Bigint &v) const {
return divmod(*this, v).first;
} Bigint operator%(const Bigint &v) const {
return divmod(*this, v).second;
} void operator/=(int v) {
if (v < )
sign = -sign, v = -v;
for (int i = (int) z.size() - , rem = ; i >= ; --i) {
long long cur = z[i] + rem * (long long) base;
z[i] = (int) (cur / v);
rem = (int) (cur % v);
}
trim();
} Bigint operator/(int v) const {
Bigint res = *this;
res /= v;
return res;
} int operator%(int v) const {
if (v < )
v = -v;
int m = ;
for (int i = z.size() - ; i >= ; --i)
m = (z[i] + m * (long long) base) % v;
return m * sign;
} void operator+=(const Bigint &v) {
*this = *this + v;
}
void operator-=(const Bigint &v) {
*this = *this - v;
}
void operator*=(const Bigint &v) {
*this = *this * v;
}
void operator/=(const Bigint &v) {
*this = *this / v;
} bool operator<(const Bigint &v) const {
if (sign != v.sign)
return sign < v.sign;
if (z.size() != v.z.size())
return z.size() * sign < v.z.size() * v.sign;
for (int i = z.size() - ; i >= ; i--)
if (z[i] != v.z[i])
return z[i] * sign < v.z[i] * sign;
return false;
} bool operator>(const Bigint &v) const {
return v < *this;
}
bool operator<=(const Bigint &v) const {
return !(v < *this);
}
bool operator>=(const Bigint &v) const {
return !(*this < v);
}
bool operator==(const Bigint &v) const {
return !(*this < v) && !(v < *this);
}
bool operator!=(const Bigint &v) const {
return *this < v || v < *this;
} void trim() {
while (!z.empty() && z.back() == )
z.pop_back();
if (z.empty())
sign = ;
} bool isZero() const {
return z.empty() || (z.size() == && !z[]);
} Bigint operator-() const {
Bigint res = *this;
res.sign = -sign;
return res;
} Bigint abs() const {
Bigint res = *this;
res.sign *= res.sign;
return res;
} long long longValue() const {
long long res = ;
for (int i = z.size() - ; i >= ; i--)
res = res * base + z[i];
return res * sign;
} friend Bigint gcd(const Bigint &a, const Bigint &b) {
return b.isZero() ? a : gcd(b, a % b);
}
friend Bigint lcm(const Bigint &a, const Bigint &b) {
return a / gcd(a, b) * b;
} void read(const string &s) {
sign = ;
z.clear();
int pos = ;
while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = s.size() - ; i >= pos; i -= base_digits) {
int x = ;
for (int j = max(pos, i - base_digits + ); j <= i; j++)
x = x * + s[j] - '';
z.push_back(x);
}
trim();
} friend istream& operator>>(istream &stream, Bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
} friend ostream& operator<<(ostream &stream, const Bigint &v) {
if (v.sign == -)
stream << '-';
stream << (v.z.empty() ? : v.z.back());
for (int i = (int) v.z.size() - ; i >= ; --i)
stream << setw(base_digits) << setfill('') << v.z[i];
return stream;
} static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + );
p[] = ;
for (int i = ; i < (int) p.size(); i++)
p[i] = p[i - ] * ;
vector<int> res;
long long cur = ;
int cur_digits = ;
for (int i = ; i < (int) a.size(); i++) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back(int(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int) cur);
while (!res.empty() && res.back() == )
res.pop_back();
return res;
} typedef vector<long long> vll; static vll karatsubaMultiply(const vll &a, const vll &b) {
int n = a.size();
vll res(n + n);
if (n <= ) {
for (int i = ; i < n; i++)
for (int j = ; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
} int k = n >> ;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end()); vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2); for (int i = ; i < k; i++)
a2[i] += a1[i];
for (int i = ; i < k; i++)
b2[i] += b1[i]; vll r = karatsubaMultiply(a2, b2);
for (int i = ; i < (int) a1b1.size(); i++)
r[i] -= a1b1[i];
for (int i = ; i < (int) a2b2.size(); i++)
r[i] -= a2b2[i]; for (int i = ; i < (int) r.size(); i++)
res[i + k] += r[i];
for (int i = ; i < (int) a1b1.size(); i++)
res[i] += a1b1[i];
for (int i = ; i < (int) a2b2.size(); i++)
res[i + n] += a2b2[i];
return res;
} Bigint operator*(const Bigint &v) const {
vector<int> a6 = convert_base(this->z, base_digits, );
vector<int> b6 = convert_base(v.z, base_digits, );
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size())
a.push_back();
while (b.size() < a.size())
b.push_back();
while (a.size() & (a.size() - ))
a.push_back(), b.push_back();
vll c = karatsubaMultiply(a, b);
Bigint res;
res.sign = sign * v.sign;
for (int i = , carry = ; i < (int) c.size(); i++) {
long long cur = c[i] + carry;
res.z.push_back((int) (cur % ));
carry = (int) (cur / );
}
res.z = convert_base(res.z, , base_digits);
res.trim();
return res;
}
}dp[][],sum[]; int main(){
scanf("%d",&T);
for(int i=;i<=;i++){
dp[i][]=;
}
for(int i=;i<=;i++){
for(int j=;j<=i;j++){
dp[i][j]=dp[i-][j]*j + dp[i-][j-]*j;
}
}
for(int i=;i<=;i++){
for(int j=;j<=i;j++){
sum[i]=sum[i]+dp[i][j];
}
}
while(T--){
scanf("%d",&n);
cout<<sum[n]<<'\n';
}
return QAQ;
}
hdu 1223
hdu1224
数据很小，dfs一遍，顺带记录一下走的路线。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int T,n,cas,maxi,m,u,v,a[];
vector<int>ve[],tmp,ans; void dfs(int x,int t){
if(x==n+){
if(t>maxi){
maxi=t;
ans.clear();
ans=tmp;
}
return;
}
for(auto y:ve[x]){
tmp.push_back(x);
dfs(y,t+a[y]);
tmp.pop_back();
}
} int main(){
scanf("%d",&T);
while(T--){
maxi=-;
tmp.clear(); ans.clear();
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
ve[i].clear();
}
a[n+]=a[];
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
ve[u].push_back(v);
}
dfs(,a[]);
cas++;
printf("CASE %d#\npoints : %d\ncircuit : ",cas,maxi);
for(auto x:ans){
printf("%d->",x);
}
printf("1\n");
if(T) printf("\n");
}
return QAQ;
}
hdu 1224
hdu1225
按题意模拟，用map计数，排序输出。
#include<bits/stdc++.h>
#define QAQ 0
#define miaojie
#ifdef miaojie
#define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#else
#define dbg(...)
#endif using namespace std; struct node{
string ss;
int r,r2,r3;
bool operator <(const node a) const{
if(r==a.r){
if(r2==a.r2){
if(r3==a.r3){
return ss<a.ss;
}
return r3>a.r3;
}
return r2>a.r2;
}
return r>a.r;
}
}; int n,a,b;
char c;
string s1,s2,s3;
map<string,int>m,m2,m3;
set<string>s; int main(){
while(cin>>n){
m.clear(); m2.clear(); m3.clear(); s.clear();
for(int i=;i<=n*(n-);i++){
cin>>s1>>s2>>s3;
cin>>a>>c>>b;
s.insert(s1); s.insert(s3);
m2[s1]=m2[s1]+a-b;
m2[s3]=m2[s3]+b-a;
m3[s1]+=a;
m3[s3]+=b;
if(a>b){
m[s1]+=;
}
else if(a==b){
m[s1]++;
m[s3]++;
}
else{
m[s3]+=;
}
} node ans[n];
int p=;
for(auto x:s){
ans[p].r=m[x];
ans[p].r2=m2[x];
ans[p].r3=m3[x];
ans[p].ss=x;
p++;
}
sort(ans,ans+p);
for(int i=;i<p;i++){
cout<<ans[i].ss<<" "<<ans[i].r<<endl;
}
cout<<'\n';
}
return QAQ;
}
hdu 1225
hdu1226
题目给了10s...从高位到低位bfs，这样保证一定从小到大，直到搜到模n为0的。模n相同的数等价，所以前面出现过的余数后面再有就不必入队了。n=0特判。
#include<bits/stdc++.h>
#define QAQ 0
#define miaojie1
#ifdef miaojie
#define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#else
#define dbg(...)
#endif using namespace std; int T,n,c,m;
char ch[];
bool f[],r[]; struct node{
int v[],l,rr;
}; void bfs(){
queue<node>q;
for(int i=;i<=;i++){
if(f[i]){
node t;
t.v[]=i;
t.rr=i%n;
if(r[t.rr]) continue;
r[t.rr]=;
t.l=;
if(!t.rr){
if(i>=){
printf("%c",i+);
}
else printf("%d",i);
return;
}
q.push(t);
}
}
while(!q.empty()){
node t=q.front();
q.pop();
for(int i=;i<=;i++){
if(f[i]){
node tt=t;
tt.rr=(tt.rr*c+i)%n;
tt.v[tt.l++]=i;
if(!tt.rr){
for(int j=;j<tt.l;j++){
if(tt.v[j]>=){
printf("%c",tt.v[j]+);
}
else printf("%d",tt.v[j]);
}
dbg(tt.l);
return;
}
if(!r[tt.rr] && tt.l<=){
r[tt.rr]=;
q.push(tt);
}
}
}
}
printf("give me the bomb please");
} int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&c,&m);
memset(f,,sizeof(f));
memset(r,,sizeof(r)); for(int i=;i<=m;i++){
scanf("%s",ch);
if(ch[]>='A'){
f[ch[]-]=;
}
else f[ch[]-]=;
}
if(n==){
if(f[]){
printf("0\n");
}
else printf("give me the bomb please\n");
continue;
}
bfs();
printf("\n");
}
return QAQ;
}
hdu 1226
hdu 1256
根据下面内圈一定是正方形推一下各个长度。题目表达的意思是竖线宽为n/6+1....读题读错了。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int T,n,a,b,d;
char c,s[]; void f(){
for(int i=;i<=d;i++){
printf(" ");
}
for(int i=;i<=b;i++){
printf("%c",c);
}
printf("\n");
} void f2(int x){
for(int i=;i<=x;i++){
for(int j=;j<=d;j++){
printf("%c",c);
}
for(int j=;j<=b;j++){
printf(" ");
}
for(int j=;j<=d;j++){
printf("%c",c);
}
printf("\n");
}
} int main(){
scanf("%d",&T);
while(T--){
scanf("%s%d",s,&n);
c=s[];
a=(n-)/,b=(n-)/,d=n/+;
f(); f2(a);
f(); f2(b);
f();
if(T) printf("\n");
}
return QAQ;
}
hdu 1256
hdu 1257
转化为求最长上升子序列。默写板子...
#include<bits/stdc++.h>
#define QAQ 0 using namespace std;
const int maxn=1e6+; int n,a[maxn],dp[maxn]; int main(){
while(scanf("%d",&n)!=EOF){
int ans=-;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
dp[i]=;
}
for(int i=;i<=n;i++){
for(int j=;j<i;j++){
if(a[i]>a[j]){
dp[i]=max(dp[j]+,dp[i]);
}
}
}
for(int i=;i<=n;i++){
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return QAQ;
}
hdu 1257
hdu 1258
又是快乐dfs，题目已经排好序了~
注意每次搜的时候去重，比如搜到50的时候，下一个和再下一个都是25，只能搜1次25。也就是同一层不能搜重复数，不然最后会有相同的疯狂刷屏.....
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int t,n,cnt,sum,a[];
vector<int>v; void dfs(int x){
if(sum>t) return;
if(sum==t){
cnt++;
for(int i=;i<v.size();i++){
printf("%d",v[i]);
if(i!=v.size()-) printf("+");
else printf("\n");
}
} int pre=-;
for(int i=x+;i<=n;i++){
if(a[i]==pre) continue;
pre=a[i];
sum+=a[i];
v.push_back(a[i]);
dfs(i);
sum-=a[i];
v.pop_back();
}
} int main(){
while(){
scanf("%d%d",&t,&n);
if(t== && n==) break;
cnt=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
printf("Sums of %d:\n",t);
dfs();
if(!cnt) printf("NONE\n");
}
return QAQ;
}
hdu 1258
hdu 1259
按题意模拟。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int n,m,x,y; int main(){
scanf("%d",&n);
while(n--){
string s="$ZJUTACM";
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
swap(s[x],s[y]);
}
for(int i=;i<=;i++){
if(s[i]=='J'){
printf("%d\n",i);
break;
}
}
}
return QAQ;
}
hdu 1259
hdu 1260
dp[i]表示让i个人买完票的最短时间。第i个人买票要么单独买，要么和前面的人合买。
状态转移方程dp[i]=min(dp[i-1]+s[i],dp[i-2]+d[i-1])。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int N,k,s[],d[],dp[]; int main(){
scanf("%d",&N);
while(N--){
bool f=;
scanf("%d",&k);
memset(dp,,sizeof(dp));
for(int i=;i<=k;i++){
scanf("%d",&s[i]);
}
for(int i=;i<=k-;i++){
scanf("%d",&d[i]);
} dp[]=s[];
for(int i=;i<=k;i++){
dp[i]=min(dp[i-]+s[i],dp[i-]+d[i-]);
}
int a=dp[k]/+,b=dp[k]/%,c=dp[k]%;
if(a>=){
a-=;
f=;
}
printf("%02d:%02d:%02d ",a,b,c);
if(f) printf("pm\n");
else printf("am\n");
}
return QAQ;
}
hdu 1260
hdu 1261
组合数公式 sigma(a)! / sigma(a!) ，爆ll了，用大数。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; const int base = ;
const int base_digits = ; struct Bigint {
vector<int> z;
int sign; Bigint() :
sign() {
} Bigint(long long v) {
*this = v;
} Bigint(const string &s) {
read(s);
} void operator=(const Bigint &v) {
sign = v.sign;
z = v.z;
} void operator=(long long v) {
sign = ;
if (v < )
sign = -, v = -v;
z.clear();
for (; v > ; v = v / base)
z.push_back(v % base);
} Bigint operator+(const Bigint &v) const {
if (sign == v.sign) {
Bigint res = v; for (int i = , carry = ; i < (int) max(z.size(), v.z.size()) || carry; ++i) {
if (i == (int) res.z.size())
res.z.push_back();
res.z[i] += carry + (i < (int) z.size() ? z[i] : );
carry = res.z[i] >= base;
if (carry)
res.z[i] -= base;
}
return res;
}
return *this - (-v);
} Bigint operator-(const Bigint &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
Bigint res = *this;
for (int i = , carry = ; i < (int) v.z.size() || carry; ++i) {
res.z[i] -= carry + (i < (int) v.z.size() ? v.z[i] : );
carry = res.z[i] < ;
if (carry)
res.z[i] += base;
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
} void operator*=(int v) {
if (v < )
sign = -sign, v = -v;
for (int i = , carry = ; i < (int) z.size() || carry; ++i) {
if (i == (int) z.size())
z.push_back();
long long cur = z[i] * (long long) v + carry;
carry = (int) (cur / base);
z[i] = (int) (cur % base);
//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
}
trim();
} Bigint operator*(int v) const {
Bigint res = *this;
res *= v;
return res;
} friend pair<Bigint, Bigint> divmod(const Bigint &a1, const Bigint &b1) {
int norm = base / (b1.z.back() + );
Bigint a = a1.abs() * norm;
Bigint b = b1.abs() * norm;
Bigint q, r;
q.z.resize(a.z.size()); for (int i = a.z.size() - ; i >= ; i--) {
r *= base;
r += a.z[i];
int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : ;
int s2 = b.z.size() - < r.z.size() ? r.z[b.z.size() - ] : ;
int d = ((long long) s1 * base + s2) / b.z.back();
r -= b * d;
while (r < )
r += b, --d;
q.z[i] = d;
} q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair(q, r / norm);
} friend Bigint sqrt(const Bigint &a1) {
Bigint a = a1;
while (a.z.empty() || a.z.size() % == )
a.z.push_back(); int n = a.z.size(); int firstDigit = (int) sqrt((double) a.z[n - ] * base + a.z[n - ]);
int norm = base / (firstDigit + );
a *= norm;
a *= norm;
while (a.z.empty() || a.z.size() % == )
a.z.push_back(); Bigint r = (long long) a.z[n - ] * base + a.z[n - ];
firstDigit = (int) sqrt((double) a.z[n - ] * base + a.z[n - ]);
int q = firstDigit;
Bigint res; for(int j = n / - ; j >= ; j--) {
for(; ; --q) {
Bigint r1 = (r - (res * * base + q) * q) * base * base + (j > ? (long long) a.z[ * j - ] * base + a.z[ * j - ] : );
if (r1 >= ) {
r = r1;
break;
}
}
res *= base;
res += q; if (j > ) {
int d1 = res.z.size() + < r.z.size() ? r.z[res.z.size() + ] : ;
int d2 = res.z.size() + < r.z.size() ? r.z[res.z.size() + ] : ;
int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : ;
q = ((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * );
}
} res.trim();
return res / norm;
} Bigint operator/(const Bigint &v) const {
return divmod(*this, v).first;
} Bigint operator%(const Bigint &v) const {
return divmod(*this, v).second;
} void operator/=(int v) {
if (v < )
sign = -sign, v = -v;
for (int i = (int) z.size() - , rem = ; i >= ; --i) {
long long cur = z[i] + rem * (long long) base;
z[i] = (int) (cur / v);
rem = (int) (cur % v);
}
trim();
} Bigint operator/(int v) const {
Bigint res = *this;
res /= v;
return res;
} int operator%(int v) const {
if (v < )
v = -v;
int m = ;
for (int i = z.size() - ; i >= ; --i)
m = (z[i] + m * (long long) base) % v;
return m * sign;
} void operator+=(const Bigint &v) {
*this = *this + v;
}
void operator-=(const Bigint &v) {
*this = *this - v;
}
void operator*=(const Bigint &v) {
*this = *this * v;
}
void operator/=(const Bigint &v) {
*this = *this / v;
} bool operator<(const Bigint &v) const {
if (sign != v.sign)
return sign < v.sign;
if (z.size() != v.z.size())
return z.size() * sign < v.z.size() * v.sign;
for (int i = z.size() - ; i >= ; i--)
if (z[i] != v.z[i])
return z[i] * sign < v.z[i] * sign;
return false;
} bool operator>(const Bigint &v) const {
return v < *this;
}
bool operator<=(const Bigint &v) const {
return !(v < *this);
}
bool operator>=(const Bigint &v) const {
return !(*this < v);
}
bool operator==(const Bigint &v) const {
return !(*this < v) && !(v < *this);
}
bool operator!=(const Bigint &v) const {
return *this < v || v < *this;
} void trim() {
while (!z.empty() && z.back() == )
z.pop_back();
if (z.empty())
sign = ;
} bool isZero() const {
return z.empty() || (z.size() == && !z[]);
} Bigint operator-() const {
Bigint res = *this;
res.sign = -sign;
return res;
} Bigint abs() const {
Bigint res = *this;
res.sign *= res.sign;
return res;
} long long longValue() const {
long long res = ;
for (int i = z.size() - ; i >= ; i--)
res = res * base + z[i];
return res * sign;
} friend Bigint gcd(const Bigint &a, const Bigint &b) {
return b.isZero() ? a : gcd(b, a % b);
}
friend Bigint lcm(const Bigint &a, const Bigint &b) {
return a / gcd(a, b) * b;
} void read(const string &s) {
sign = ;
z.clear();
int pos = ;
while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = s.size() - ; i >= pos; i -= base_digits) {
int x = ;
for (int j = max(pos, i - base_digits + ); j <= i; j++)
x = x * + s[j] - '';
z.push_back(x);
}
trim();
} friend istream& operator>>(istream &stream, Bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
} friend ostream& operator<<(ostream &stream, const Bigint &v) {
if (v.sign == -)
stream << '-';
stream << (v.z.empty() ? : v.z.back());
for (int i = (int) v.z.size() - ; i >= ; --i)
stream << setw(base_digits) << setfill('') << v.z[i];
return stream;
} static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + );
p[] = ;
for (int i = ; i < (int) p.size(); i++)
p[i] = p[i - ] * ;
vector<int> res;
long long cur = ;
int cur_digits = ;
for (int i = ; i < (int) a.size(); i++) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back(int(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int) cur);
while (!res.empty() && res.back() == )
res.pop_back();
return res;
} typedef vector<long long> vll; static vll karatsubaMultiply(const vll &a, const vll &b) {
int n = a.size();
vll res(n + n);
if (n <= ) {
for (int i = ; i < n; i++)
for (int j = ; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
} int k = n >> ;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end()); vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2); for (int i = ; i < k; i++)
a2[i] += a1[i];
for (int i = ; i < k; i++)
b2[i] += b1[i]; vll r = karatsubaMultiply(a2, b2);
for (int i = ; i < (int) a1b1.size(); i++)
r[i] -= a1b1[i];
for (int i = ; i < (int) a2b2.size(); i++)
r[i] -= a2b2[i]; for (int i = ; i < (int) r.size(); i++)
res[i + k] += r[i];
for (int i = ; i < (int) a1b1.size(); i++)
res[i] += a1b1[i];
for (int i = ; i < (int) a2b2.size(); i++)
res[i + n] += a2b2[i];
return res;
} Bigint operator*(const Bigint &v) const {
vector<int> a6 = convert_base(this->z, base_digits, );
vector<int> b6 = convert_base(v.z, base_digits, );
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size())
a.push_back();
while (b.size() < a.size())
b.push_back();
while (a.size() & (a.size() - ))
a.push_back(), b.push_back();
vll c = karatsubaMultiply(a, b);
Bigint res;
res.sign = sign * v.sign;
for (int i = , carry = ; i < (int) c.size(); i++) {
long long cur = c[i] + carry;
res.z.push_back((int) (cur % ));
carry = (int) (cur / );
}
res.z = convert_base(res.z, , base_digits);
res.trim();
return res;
}
}; int n; int main(){
while(scanf("%d",&n)){
if(n==) break;
Bigint ans=;
int a[],cnt=;
for(int i=;i<=n;i++){
cin>>a[i];
cnt+=a[i];
}
for(int i=;i<=cnt;i++){
ans*=i;
}
for(int i=;i<=n;i++){
for(int j=;j<=a[i];j++){
ans/=j;
}
}
cout<<ans<<endl;
}
return QAQ;
}
hdu 1261
hdu 1262
线性筛预处理一下素数，从m/2开始搜，第一个搜到的一定是最近的。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std;
const int maxn=;
int prime[maxn],check[maxn];
int m,n; void xxs(){
int tot=;
memset(check,,sizeof(check));
check[]=;
for(int i=;i<maxn;i++){
if(!check[i]) prime[tot++]=i;
for(int j=;j<tot;j++){
if(i*prime[j]>maxn) break;
check[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
} int main(){
xxs();
while(scanf("%d",&m)!=EOF){
n=m/;
while(){
if(!check[n] && !check[m-n]){
printf("%d %d\n",n,m-n);
break;
}
n--;
}
}
return QAQ;
}
hdu 1262
hdu 1263
二维map计数。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int N,M,a;
map<string,map<string,int> >m;
string s1,s2; int main(){
cin>>N;
while(N--){
m.clear();
cin>>M;
for(int i=;i<=M;i++){
cin>>s1>>s2>>a;
m[s2][s1]+=a;
}
for(auto x:m){
cout<<x.first<<'\n';
for(auto y:x.second){
cout<<" |----"<<y.first<<'('<<y.second<<')'<<'\n';
}
}
if(N) cout<<'\n';
}
return QAQ;
}
hdu 1263
hdu 1264
注意数据范围0到100...直接暴力扫。确定矩形位置的两个点有两种情况，一开始没swap掉坑里了。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int a1,b1,a2,b2;
bool m[][]; int main(){
while(){
memset(m,,sizeof(m));
int cnt=;
while(){
scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
if(a1==- || a1==-) break;
if(a1>a2) swap(a1,a2);
if(b1>b2) swap(b1,b2); for(int i=b1;i<b2;i++){
for(int j=a1;j<a2;j++){
if(!m[i][j]){
cnt++;
m[i][j]=;
}
}
}
}
printf("%d\n",cnt);
if(a1==-) break;
}
return QAQ;
}
hdu 1264
hdu 1265
十六进制表示浮点数...挺奇特的...完全没想到这个思路。直接把计算机存放的二进制化成十六进制。。。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int N;
float f; int main(){
scanf("%d",&N);
while(N--){
scanf("%f",&f);
unsigned char *p=(unsigned char *)&f;
printf("%02X%02X%02X%02X\n",p[],p[],p[],p[]);
}
return QAQ;
}
hdu 1265
hdu 1491
模拟题。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std; int T,a,b;
int m[]={,,,,,,,,,,,,}; int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&a,&b);
if(a> || (a==&&b>)){
printf("What a pity, it has passed!\n");
}
else if(a== && b==){
printf("It's today!!\n");
}
else{
if(a==){
printf("%d\n",-b);
}
else{
int ans=+m[a]-b;
for(int i=a+;i<=;i++){
ans+=m[i];
}
printf("%d\n",ans);
}
}
}
return QAQ;
}
hdu 1491
hdu 1492
因子只有2，3，5，7。统计它们的幂次，用求因数个数的公式就好。不开ll会wa。
#include<bits/stdc++.h>
#define QAQ 0 using namespace std;
typedef long long ll; ll n;
ll f[]={,,,},cnt[]; int main(){
while(){
scanf("%lld",&n);
if(n==) break;
ll ans=;
for(int i=;i<;i++){
ll t=n;
cnt[i]=;
while(t%f[i]==){
cnt[i]++;
t/=f[i];
}
ans*=(cnt[i]+);
}
printf("%lld\n",ans);
}
return QAQ;
}
hdu 1492
hdu 1493
概率dp。本来想开二维，其实可以滚动，每次的概率以上次为基础。每次从后往前，dp[i]=dp[i]+dp[i-k]*rp[k]，k为掷出的点数。
#include<bits/stdc++.h>
#define QAQ 0
#define miaojie1
#ifdef miaojie
#define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#else
#define dbg(...)
#endif using namespace std; int T;
double rp[],dp[];
int a[]={,,,,,,,,,,}; int main(){
scanf("%d",&T); while(T--){
for(int i=;i<=;i++){
scanf("%lf",&rp[i]);
}
memset(dp,,sizeof(dp));
dp[]=; for(int i=;i<=;i++){
dbg(dp[]);
for(int j=;j>;j--){
dp[j]=;
for(int k=;k<=;k++){
if(j<k) break;
dp[j]=dp[j]+rp[k]*dp[j-k];
}
}
}
for(int i=;i<=;i++){
printf("%d: %.1lf%%\n",a[i],100.0*dp[a[i]]);
}
if(T) printf("\n");
}
return QAQ;
}
hdu 1493
hdu 1494
还是dp。把n圈展开成线，能量看成0-14的整数，dp[i][j]表示到第i段时有j格能量所用的最短时间，顺序dp。注意j=0一定是刚用过加速卡，j=10可能是普通行驶或爆卡，j>10一定是普通行驶...分类挺麻烦的，状态方程分四个。感觉还可以简化下。
#include<bits/stdc++.h>
#define QAQ 0
#define miaojie1
#ifdef miaojie
#define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#else
#define dbg(...)
#endif using namespace std;
typedef long long ll; int l,n;
ll a[],b[],dp[][]; int main(){
while(scanf("%d",&l)!=EOF){
scanf("%d",&n);
int sum=n*l;
for(int i=;i<=l;i++){
scanf("%d",&a[i]);
for(int j=;j<=n-;j++){
a[i+j*l]=a[i];
}
}
for(int i=;i<=l;i++){
scanf("%d",&b[i]);
for(int j=;j<=n-;j++){
b[i+j*l]=b[i];
}
}
for(int i=;i<=sum;i++){
for(int j=;j<;j++){
dp[i][j]=1ll<<;
}
}
dp[][]=; for(int i=;i<=sum;i++){
for(int j=;j<;j++){
if(j==) {
dp[i][j]=dp[i-][]+b[i];
}
else if(j==){
dp[i][j]=min( dp[i-][]+a[i] , dp[i-][]+a[i] );
}
else if(j>){
dp[i][j]=dp[i-][j-]+a[i];
}
else dp[i][j]=min( dp[i-][j-]+a[i] , dp[i-][j+]+b[i] );
}
}
ll ans=1ll<<;
for(int i=;i<;i++){
ans=min(ans,dp[sum][i]);
dbg(dp[sum][i]);
}
printf("%lld\n",ans);
}
return QAQ;
}
hdu 1494
hdu 1495
bfs，模拟每步的六种操作即可。
#include<bits/stdc++.h>
#define miaojie1
#ifdef miaojie
#define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#else
#define dbg(...)
#endif using namespace std; int S,s,n,m;
bool vis[][][]; struct node{
int a,b,c,r;
node(){}
node(int _a,int _b,int _c,int _r) : a(_a),b(_b),c(_c),r(_r){}
}; void bfs(){
memset(vis,,sizeof(vis));
if(S%){
printf("NO\n");
return;
}
else s=S/;
queue<node>q;
node st(S,,,);
q.push(st);
vis[s][][]=; while(!q.empty()){
node t=q.front();
dbg(t.a,t.b,t.c,t.r);
if( (t.a==s&&t.b==s) || (t.a==s&&t.c==s) || (t.b==s&&t.c==s)){
printf("%d\n",t.r);
return;
}
q.pop();
if(t.a>){
node p=t;
if(p.a>=n-p.b){
p.a=p.a-(n-p.b);
p.b=n;
p.r++;
}
else{
p.b+=p.a;
p.a=;
p.r++;
}
if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=; p=t;
if(p.a>=m-p.c){
p.a=p.a-(m-p.c);
p.c=m;
p.r++;
}
else{
p.c+=p.a;
p.a=;
p.r++;
}
if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=; p=t;
if(p.b>=S-p.a){
p.b=p.b-(S-p.a);
p.a=s;
p.r++;
}
else{
p.a+=p.b;
p.b=;
p.r++;
}
if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=; p=t;
if(p.b>=m-p.c){
p.b=p.b-(m-p.c);
p.c=m;
p.r++;
}
else{
p.c+=p.b;
p.b=;
p.r++;
}
if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=; p=t;
if(p.c>=S-p.a){
p.c=p.c-(S-p.a);
p.a=s;
p.r++;
}
else{
p.a+=p.c;
p.c=;
p.r++;
}
if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=; p=t;
if(p.c>=n-p.b){
p.c=p.c-(n-p.b);
p.b=n;
p.r++;
}
else{
p.b+=p.c;
p.c=;
p.r++;
}
if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=;
}
}
printf("NO\n");
} int main(){
while(){
scanf("%d%d%d",&S,&n,&m);
if(S== && n== && m==) break;
bfs();
}
return ;
}
hdu 1495
hdu 1496
四个for显然超了，用折半法降时间复杂度，结果还是T，加了特判才过。由于有平方，只讨论正号省时间，最后乘16就行。
#include<bits/stdc++.h> using namespace std;
typedef long long ll; int a,b,c,d;
map<int,int>mp; int main(){
while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){
if((a> && b> && c> && d>) || (a< && b< && c< && d<)){
printf("0\n");
continue;
}
ll ans=;
mp.clear();
for(int i=;i<=;i++){
for(int j=;j<=;j++){
mp[a*i*i+b*j*j]++;
}
}
for(int i=;i<=;i++){
for(int j=;j<=;j++){
ans+=mp[-(c*i*i+d*j*j)];
}
}
ans*=;
printf("%lld\n",ans);
}
return ;
}
hdu 1496
hdu 1497
怎么又是大模拟，8想做！不看它了！
hdu 1498
行对列匹配跑一遍二分图的最小覆盖,balabala（明天补上）
第二天：好像也补不上啥啊。。多一个匹配就多一个既不同行也不同列的气球，超过k个就不行了。
#include<bits/stdc++.h>
#define miaojie1
#ifdef miaojie
#define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#else
#define dbg(...)
#endif
using namespace std; int n,k,a[][],edge[][],cx[],cy[],ans[],pp;
bool vis[];
set<int>se; int line(int u){
for(int v=;v<=n;v++){
if(edge[u][v] && !vis[v]){
vis[v]=;
if(cy[v]==- || line(cy[v])){
cx[u]=v;
cy[v]=u;
return ;
}
}
}
return ;
} int mincover(){
int ret=;
memset(cx,-,sizeof(cx));
memset(cy,-,sizeof(cy));
for(int i=;i<=n;i++){
if(cx[i]==-){
memset(vis,,sizeof(vis));
ret+=line(i);
}
}
return ret;
} int main(){
while(){
scanf("%d%d",&n,&k);
se.clear(); pp=;
if(n== && k==) break;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&a[i][j]);
se.insert(a[i][j]);
}
}
for(auto x:se){
dbg(x);
memset(edge,,sizeof(edge));
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(a[i][j]==x){
edge[i][j]=;
}
}
}
if(mincover()>k) ans[pp++]=x;
}
dbg(pp);
if(pp==){
printf("-1\n");
}
else{
for(int i=;i<pp;i++){
printf("%d",ans[i]);
if(i!=pp-) printf(" ");
else printf("\n");
}
}
}
return ;
}
hdu 1498
hdu 1728
一开始传统bfs，出队一个就搜四周，记录朝向来表示是否转弯，mle了。
其实这题应该换个想法，答案只和拐弯数有关，所以搜的时候可以不再前进一个点，改为一直走到某方向的尽头，路上的点还是判vis按顺序入队。这样每个点搜出一个十字形状，并且保证了第一次搜到时拐弯数最小。
定义了y1，没敢用万能头文件。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std; int T,m,n;
char a[][];
bool vis[][];
int k,x1,x2,y1,y2;
int tx[]={,-,,,},ty[]={,,,,-}; struct node{
int x,y,r;
node(){}
node(int _x,int _y,int _r) : x(_x),y(_y),r(_r){}
}; void bfs(){
queue<node>q;
vis[x1][y1]=;
// node st1(x1,y1,-1,1),st2(x1,y1,-1,2),st3(x1,y1,-1,3),st4(x1,y1,-1,4);
// q.push(st1); q.push(st2); q.push(st3); q.push(st4);
node st(x1,y1,-);
q.push(st);
while(!q.empty()){
node t=q.front();
// cout<<"!!!"<<t.x<<" "<<t.y<<" "<<t.r<<" "<<endl;
q.pop();
if(t.r>k) continue;
if(t.x==x2 && t.y==y2){
// cout<<"~~~"<<t.r<<" "<<t.s<<endl;
printf("yes\n");
return;
}
for(int i=;i<=;i++){
node p=t;
p.x+=tx[i];
p.y+=ty[i];
p.r++;
while(!(p.x<||p.x>m||p.y<||p.y>n||p.r>k||a[p.x][p.y]=='*')){
if(!vis[p.x][p.y]){
vis[p.x][p.y]=;
q.push(p);
}
p.x+=tx[i];
p.y+=ty[i];
}
}
}
printf("no\n");
} int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&m,&n);
memset(vis,,sizeof(vis));
for(int i=;i<=m;i++){
for(int j=;j<=n;j++){
cin>>a[i][j];
}
}
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
bfs();
}
return ;
}
hdu 1728
hdu 1729
sg函数太生疏了.....
s为容量，找到临界点t+t*t<s且(t+1)+(t+1)^2>=s，可知当盒子里大于t个时必胜，返回容量减现有个数（类比取石子），等于t时必败。小于t时无法判断，但s和t都是必败点，返回（t，c）等价。
#include<bits/stdc++.h>
using namespace std;
int n,cnt,s,c;
int SG(int s,int c){
int t=sqrt(s);
while(t+t*t>=s){
t--;
}
if(c>t) return s-c;
else return SG(t,c);
}
int main(){
while(){
scanf("%d",&n);
if(n==) break;
int ans=;
for(int i=;i<=n;i++){
scanf("%d%d",&s,&c);
ans^=SG(s,c);
}
printf("Case %d:\n",++cnt);
if(ans) printf("Yes\n");
else printf("No\n");
}
return ;
}
hdu 1729
hdu 1730
这题友好多了，每行两个棋子的距离-1其实就类比每堆石子数，nim一下就好。
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
int ans=;
for(int i=;i<=n;i++){
scanf("%d%d",&a,&b);
ans=ans^(abs(a-b)-);
}
if(!ans){
printf("BAD LUCK!\n");
}
else printf("I WIN!\n");
}
return ;
}
hdu 1730
hdu 1732
bfs，记录人和三个箱子的位置。走一步——是否有障碍或箱子——若有箱子，箱子后面是否有障碍或其他箱子。
因为把=写成==爆内存了，找了一个小时，强行拉底ac率，很烦。
#include<bits/stdc++.h>
using namespace std;
struct node{
int x[],y[],r;
}st;
int n,m;
int tx[]={-,,,},ty[]={,,,-},endx[],endy[];
char a[][];
bool vis[][][][][][][][];
queue<node>q;
void bfs(){
memset(vis,,sizeof(vis));
while(!q.empty()) q.pop();
q.push(st);
while(!q.empty()){
node t=q.front();
q.pop();
bool check=;
for(int i=;i<=;i++){
bool ck=;
for(int j=;j<=;j++){
if(t.x[i]==endx[j] && t.y[i]==endy[j]) ck=;
}
if(!ck){
check=;
break;
}
}
if(check){
printf("%d\n",t.r);
return;
}
if(vis[t.x[]][t.y[]][t.x[]][t.y[]][t.x[]][t.y[]][t.x[]][t.y[]]==) continue;
vis[t.x[]][t.y[]][t.x[]][t.y[]][t.x[]][t.y[]][t.x[]][t.y[]]==;
for(int i=;i<=;i++){
node p=t;
int f=;
p.x[]+=tx[i];
p.y[]+=ty[i];
p.r++;
if(a[p.x[]][p.y[]]=='#'||p.x[]>=n||p.x[]<||p.y[]>=m||p.y[]<) continue;
for(int j=;j<=;j++){
if(p.x[]==p.x[j] && p.y[]==p.y[j]){
f=j;
break;
}
}
if(f){
p.x[f]+=tx[i];
p.y[f]+=ty[i];
if(a[p.x[f]][p.y[f]]=='#'||p.x[f]>=n||p.x[f]<||p.y[f]>=m||p.y[f]<) continue;
bool ff=;
for(int j=;j<=;j++){
if(j==f) continue;
if(p.x[f]==p.x[j] && p.y[f]==p.y[j]){
ff=;
break;
}
}
if(!ff) q.push(p);
}
else{
q.push(p);
}
}
}
printf("-1\n");
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
while(cin>>n>>m){
int p=,q=;
for(int i=;i<n;i++){
for(int j=;j<m;j++){
cin>>a[i][j];
if(a[i][j]=='X'){
st.x[]=i;
st.y[]=j;
}
else if(a[i][j]=='*'){
st.x[++p]=i;
st.y[p]=j;
}
else if(a[i][j]=='@'){
endx[++q]=i;
endy[q]=j;
}
}
}
st.r=;
bfs();
}
return ;
}
hdu 1732
hdu 5702
排序。
#include<bits/stdc++.h>
using namespace std;
struct node{
char s[];
int v;
bool operator < (const node &t) const{
return v>t.v;
}
}a[];
int T,n;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s%d",a[i].s,&a[i].v);
}
sort(a+,a++n);
for(int i=;i<=n;i++){
printf("%s",a[i].s);
if(i==n) printf("\n");
else printf(" ");
}
}
return ;
}
hdu 5702
hdu 5703
列出前几项就能发现规律。
#include<bits/stdc++.h>
using namespace std;
int T,n;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
printf("");
for(int i=;i<=n-;i++){
printf("");
}
printf("\n");
}
return ;
}
hdu 5703
hdu 5704
方程列出来，解方程。
#include<bits/stdc++.h> using namespace std; int T,n,sum,a[];
map<int,int>m; int main(){
scanf("%d",&T);
while(T--){
m.clear(); sum=;
scanf("%d",&n);
for(int i=;i<=n-;i++){
scanf("%d",&a[i]);
m[a[i]]++;
sum+=a[i];
}
int ans=*sum/(*n-);
double p=1.0/(m[ans]+1.0);
printf("%d %.2lf\n",ans,p);
}
return ;
}
hdu 5704
hdu 5705
计算时针和分针的移动速度，从00：00：00开始枚举判断角度。为了避开精度问题乘了11。
#include<bits/stdc++.h>
using namespace std;
int h,m,s,a,cas,ansh,ansm,anss;
int main(){
ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
while(~scanf("%d:%d:%d%d",&h,&m,&s,&a)){
printf("Case #%d: ",++cas);
int t=(h*+m*+s)*,tim=,cnt=;
while(){
tim+=;
cnt+=;
int tmp=cnt%;
if(tmp>) tmp=-tmp;
if(tmp==a*&&tim>t) break;
}
tim/=;
tim=tim%(**);
ansh=tim/;
ansm=(tim-ansh*)/;
anss=tim-ansh*-ansm*;
printf("%02d:%02d:%02d\n",ansh,ansm,anss);
}
return ;
}
hdu 5705
hdu 5706
dfs连通块，搜就行了。
#include<bits/stdc++.h> using namespace std; int T,n,m,ans1,ans2;
char a[][];
char s1[]="girl",s2[]="cat"; void dfs1(int i,int j,int k){
if(i<||i>n||j<||j>m) return;
if(a[i][j]==s1[k]){
k++;
if(k==){
ans1++;
return;
}
dfs1(i-,j,k);
dfs1(i+,j,k);
dfs1(i,j+,k);
dfs1(i,j-,k);
}
} void dfs2(int i,int j,int k){
if(i<||i>n||j<||j>m) return;
if(a[i][j]==s2[k]){
k++;
if(k==){
ans2++;
return;
}
dfs2(i-,j,k);
dfs2(i+,j,k);
dfs2(i,j+,k);
dfs2(i,j-,k);
}
} int main(){
scanf("%d",&T);
while(T--){
ans1=ans2=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%s",a[i]+);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]=='g') dfs1(i,j,);
if(a[i][j]=='c') dfs2(i,j,);
}
}
printf("%d %d\n",ans1,ans2);
}
return ;
}
hdu 5706
hdu 5707
由于c中所有字母都要使用，按顺序对于每个字母判断是否能加入即可。dp两维分别表示a和b能匹配的字母数。
#include<bits/stdc++.h> using namespace std; bool dp[][];
char a[],b[],c[]; int main(){
while(~scanf("%s%s%s",a,b,c)){
int la=strlen(a),lb=strlen(b),lc=strlen(c);
if(lc!=la+lb){
printf("No\n");
continue;
}
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=la;i++){
for(int j=;j<=lb;j++){
if(c[i+j]==a[i]){
dp[i+][j]|=dp[i][j];
}
if(c[i+j]==b[j]){
dp[i][j+]|=dp[i][j];
}
}
}
if(dp[la][lb]) printf("Yes\n");
else printf("No\n");
}
return ;
}
hdu 5707
hdu5708
sg打表找规律.....看了半天，周期居然是2*（k+1）。k=1需要特判。
#include<bits/stdc++.h> using namespace std;
const int N=; int T,q,k,n,m;
int sg[][]; void get_SG(){
sg[][]=;
for(int i=;i<=N;i+=){
sg[i][]=sg[][i]=;
sg[i+][]=sg[][i+]=;
}
for(int i=;i<=N;i++){
for(int j=;j<=N;j++){
if(!sg[i-][j] || !sg[i][j-] || (i-k> && j-k> && (!sg[i-k][j-k])) )
sg[i][j]=;
else sg[i][j]=;
}
}
} void p1(){
printf("Alice\n");
} void p2(){
printf("Bob\n");
} int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&q,&k);
/* memset(sg,0,sizeof(sg));
get_SG();
printf("!!!\n");
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
printf("%d ",sg[i][j]);
}
printf("\n");
}
printf("!!!\n\n"); */ while(q--){
scanf("%d%d",&n,&m);
int l=min(n,m),s=n+m;
if(k==){
if(l%){
if(s%) p1();
else p2();
}
else p1();
continue;
}
int t=(k+)*;
if(l%t>=&&l%t<=k){
if(s%) p1();
else p2();
}
else if(l%(k+)==){
p1();
}
else{
if(s%) p2();
else p1();
}
}
}
return ;
}
hdu 5708
hdu 5710
容易发现0~4乘2后不损失值，5~9乘2后损失9。设大于5的部分长为l，得到S(n)与l的比例关系，显然约分后数字最小。从低位开始放数字，让低位的尽量大。
#include<bits/stdc++.h>
using namespace std;
int ans[],p,a,b,T,s,l;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&a,&b);
p=;
s=*b;
l=*b-a;
int t=__gcd(s,l);
s/=t; l/=t;
s=s-l*;
if(l<||s<){
puts("");
continue;
}
for(int i=;i<=l;i++){
ans[++p]=+min(s,);
s=s-min(s,);
}
while(s){
ans[++p]=min(s,);
s=s-min(s,);
}
for(int i=p;i>=;i--){
printf("%d",ans[i]);
}
printf("\n");
}
return ;
}
hdu 5710
hdu 6023
水题，模拟。
#include<bits/stdc++.h> using namespace std; int T,n,m,r,a,b,ans,cnt,pen[];
char c;
string s;
bool f[]; int main(){
ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
cin>>T;
while(T--){
cin>>n>>m;
memset(f,,sizeof(f));
memset(pen,,sizeof(pen));
ans=; cnt=;
while(m--){
cin>>r>>a>>c>>b>>s;
r-=;
if(f[r]) continue;
if(s[]=='A'){
cnt++;
f[r]=;
ans=ans+a*+b+pen[r];
}
else{
pen[r]+=;
}
}
cout<<cnt<<" "<<ans<<'\n';
}
return ;
}
hdu 6023
hdu 6024
dp[i][j]为前i个的最小花费，j=1表示第i个建，j=0表示不建。转移如下。其中dp[i][0]需要遍历一遍前面的情况。
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
struct node{
ll x,c;
bool operator < (const node &t) const{
return x<t.x;
}
}a[]; ll n,dp[][]; int main(){
while(~scanf("%lld",&n)){
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
scanf("%lld%lld",&a[i].x,&a[i].c);
}
sort(a+,a++n);
dp[][]=a[].c;
dp[][]=(1ll<<);
for(int i=;i<=n;i++){
dp[i][]=min(dp[i-][],dp[i-][])+a[i].c;
dp[i][]=(1ll<<);
ll tmp=;
for(int j=i-;j>=;j--){
tmp=tmp+(i-j)*(a[j+].x-a[j].x);
dp[i][]=min(dp[i][],dp[j][]+tmp);
}
}
printf("%lld\n",min(dp[n][],dp[n][]));
}
return ;
}
hdu 6024
hdu 6025
预处理前缀和后缀gcd，根据gcd的性质可以O(n)扫一遍得出答案。
#include<bits/stdc++.h> using namespace std;
const int maxn=1e5+; int n,T,a[maxn],pre[maxn],las[maxn],ans; int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
pre[]=a[]; las[n]=a[n];
for(int i=;i<=n;i++){
pre[i]=__gcd(pre[i-],a[i]);
}
for(int i=n-;i>=;i--){
las[i]=__gcd(las[i+],a[i]);
} ans=max(pre[n-],las[]);
for(int i=;i<=n-;i++){
ans=max(ans,__gcd(pre[i-],las[i+]));
}
printf("%d\n",ans);
}
return ;
}
hdu 6025
hdu 6026
稍微修改一下djkstra板子，记录0到每个点的最短路有几条，由于最后一定各保留一条最短路，相乘即为选择的方案数。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define miaojie1
#ifdef miaojie
#define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const ll mod=1e9+;
const int maxn=; struct edge{
int nxt,to,cost;
}e[maxn]; int n,head[],d[],cnt[],p;
ll ans;
char s[];
bool vis[];
priority_queue<pii,vector<pii>,greater<pii> >q; void addedge(int from,int to,int cost){
e[p].nxt=head[from];
e[p].to=to;
e[p].cost=cost;
head[from]=p++;
} void DJ(){
while(!q.empty()) q.pop();
for(int i=;i<n;i++){
vis[i]=;
d[i]=inf;
cnt[i]=;
}
d[]=;
q.push(make_pair(,));
while(!q.empty()){
pii t=q.top();
dbg(t.first,t.second);
q.pop();
vis[t.second]=;
for(int i=head[t.second];~i;i=e[i].nxt){
if(vis[e[i].to]) continue;
if(d[e[i].to]>t.first+e[i].cost){
d[e[i].to]=t.first+e[i].cost;
cnt[e[i].to]=;
q.push(make_pair(d[e[i].to],e[i].to));
}
else if(d[e[i].to]==t.first+e[i].cost) cnt[e[i].to]++;
}
}
} int main(){
while(~scanf("%d",&n)){
memset(head,-,sizeof(head)); p=; ans=;
for(int i=;i<n;i++){
scanf("%s",s);
for(int j=;j<n;j++){
if(s[j]!='') addedge(i,j,s[j]-);
}
}
DJ();
for(int i=;i<n;i++){
ans=ans*cnt[i]%mod;
}
printf("%lld\n",ans);
}
return ;
}
hdu 6026
hdu 6027
水题，预处理一下暴力能过。
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
const ll mod=1e9+; int T;
ll n,k,f[][]; void init(){
for(int i=;i<=;i++){
f[i][]=;
for(int j=;j<=;j++){
f[i][j]=f[i][j-]*i%mod;
}
}
} int main(){
scanf("%d",&T);
init();
while(T--){
scanf("%lld%lld",&n,&k);
ll ans=;
for(int i=;i<=n;i++){
ans=(ans+f[i][k])%mod;
}
printf("%lld\n",ans);
}
return ;
}
hdu 6027
hdu 6029
寻找是否存在完美匹配，从后往前贪心即可，尽量让后面的连接。
#include<bits/stdc++.h>
using namespace std;
int T,n,a[];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
int cnt=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==) cnt++;
}
if(n%||cnt<n/){
printf("No\n");
continue;
}
int f=;
bool jd=;
for(int i=n;i>=;i--){
if(a[i]==) f--;
else f++;
if(f<){
jd=;
break;
}
}
if(jd) printf("Yes\n");
else printf("No\n");
}
return ;
}
hdu 6029
hdu 6030
红记为1，蓝记为0，题目条件转化为连续2个或3个珠子中1的个数>=0的个数。考虑在2个连续的珠子后增加一个，有10-->101->01 , 01->011->11 , 11->111或110->11或10；
记末尾10的个数为f(a)，末尾01的个数为f(b)，末尾11的个数为f(c)，总个数f(n)；
则f(a+1)=f(c)，f(b+1)=f(a)，f(c+1)=f(b)+f(c)；
根据以上关系推出f(n)=f(n-1)+f(n-3)，显然可以用矩阵快速幂解决。
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
const int mod=1e9+;
const int z = ; int T;
ll n;
struct ju{
long long a[z][z];
}; ju muli(ju A,ju B){
ju C;
for(int i=;i<z;++i){
for(int j=;j<z;++j){
C.a[i][j]=;
for(int k=;k<z;++k){
C.a[i][j]+=A.a[i][k]*B.a[k][j];
C.a[i][j]%=mod;
}
}
}
return C;
}
ju init(){
ju res;
for(int i=;i<z;++i){
for(int j=;j<z;++j){
if(i==j)res.a[i][j]=;
else res.a[i][j]=;
}
}
return res;
}
ju pow(ju A,ll n){
ju res=init(),temp=A;
for(;n;n/=){
if(n&)res=muli(res,temp);
temp=muli(temp,temp);
}
return res;
}
void print(ju A){
for(int i=;i<z;++i){
for(int j=;j<z;++j){
cout<<A.a[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
} int main(){
scanf("%d",&T);
while(T--){
scanf("%lld",&n);
if(n==) {
printf("3\n");
continue;
}
if(n==){
printf("4\n");
continue;
}
ju ans,t;
for(int i=;i<z;i++){
for(int j=;j<z;j++){
ans.a[i][j]=t.a[i][j]=;
}
}
ans.a[][]=; ans.a[][]=; ans.a[][]=;
t.a[][]=t.a[][]=t.a[][]=t.a[][]=;
// print(t);
ans=muli(pow(t,n-),ans);
// print(ans);
printf("%lld\n",ans.a[][]%mod);
}
return ;
}
hdu 6030
hdu 6032
在贾老板的指导下勉强混过了。
三个map分别存子串是否出现、出现次数、对应的sg。结构体存胜负，顺便存分数，dfs跑sg的时候记得每次交换自己(p1)和对手(p2)。做着难受，I very vegetable.
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define miaojie1
#ifdef miaojie
#define dbg(args...) do {cout << #args << " : "; err(args);} while (0)
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#else
#define dbg(...)
#endif
using namespace std; struct node{
int flag;
int p1,p2;
node(){}
node(bool _flag,int _p1,int _p2) : flag(_flag),p1(_p1),p2(_p2){}
bool operator < (const node &a)const{
if(flag==a.flag){
if(p2==a.p2){
return p1<a.p1;
}
return p2>a.p2;
}
return flag<a.flag;
}
}; map<string,int>jd;
map<string,set<int> >cnt;
map<string,node>sg;
int n;
char s[]; node dfs(string s){
if(sg.count(s)){
return sg[s];
}
node t{,inf,};
string ts;
for(char i='a';i<='z';i++){
if(jd.count(s+i)) t=min(t,dfs(s+i));
if(jd.count(i+s)) t=min(t,dfs(i+s));
} int sum=,maxi=;
for(int i=;i<s.size();i++){
sum=sum+s[i]-;
maxi=max(maxi,s[i]-);
}
sum=sum*maxi+cnt[s].size();
dbg(s,t.flag,t.p1,t.p2,sum);
if(t.p1==inf){
node tt(,,sum);
return tt;
}
sg[s].flag=-t.flag;
sg[s].p1=t.p2;
sg[s].p2=t.p1+sum;
return sg[s];
} int main(){
while(~scanf("%d",&n)){
jd.clear(); cnt.clear(); sg.clear();
for(int i=;i<=n;i++){
scanf("%s",&s);
int l=strlen(s);
for(int j=;j<l;j++){
string t;
for(int k=j;k<l;k++){
t+=s[k];
jd[t]=;
cnt[t].insert(i);
}
}
}
node ans=dfs("");
if(ans.flag) printf("Alice\n");
else printf("Bob\n");
printf("%d %d\n",ans.p1,ans.p2);
}
return ;
}
hdu 6032