SGU 125
题意：给你一个数组b[i][j],表示i,j的四周有多少个数字大于它的，问你能不能构造出一个a矩形
收获：dfs + 剪枝
一行一行的dfs，然后第一行去枚举0-9，下一行判断当前选择能否满足上一行对应列的情况，可以的话就继续dfs
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e5+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int a[6][6],n,b[6][6]; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; bool ok(int x,int y){ int ret = 0; // dd(x)dd(y)de(ret) rep(i,0,4) if(a[x+dx[i]][y+dy[i]] > a[x][y]) ret++; return ret==b[x][y]; } bool dfs(int x,int y){ // dd(n)dd(x)de(y) int tx = x,ty = y + 1; if(x > n){ rep(i,1,n+1) if(!ok(n,i)) return false; rep(i,1,n+1) rep(j,1,n+1) printf("%d%c",a[i][j]," "[j==n]); return true; } if(ty > n) ty = 1,tx = x + 1; rep(i,0,10){ a[x][y] = i; if(x != 1) if(!ok(x-1,y)) continue; if(dfs(tx,ty)) return true; } return false; } int main(){ scanf("%d",&n); rep(i,1,n+1) rep(j,1,n+1) scanf("%d",&b[i][j]); if(!dfs(1,1)) puts("NO SOLUTION"); return 0; }
SGU 358
题意：求中位数的中位数
收获：无
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e5+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int a[maxn]; vector<int> ans; int main(){ rep(i,0,3){ rep(j,0,3) scanf("%d",&a[j]); sort(a,a+3); ans.pb(a[1]); } sort(all(ans)); printf("%d ",ans[1]); return 0; }
SGU 193
题意：给你一个N，让你求最大一个数字b，gcd(n,b)==1,(1<=b<n/2)
收获：不是奇数就是偶数，判断一下就行了
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e5+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int compare(string str1,string str2) { if(str1.length()>str2.length()) return 1; else if(str1.length()<str2.length()) return -1; else return str1.compare(str2); } //高精度加法 //只能是两个正数相加 string add(string str1,string str2)//高精度加法 { string str; int len1=str1.length(); int len2=str2.length(); //前面补0，弄成长度相同 if(len1<len2) { for(int i=1;i<=len2-len1;i++) str1="0"+str1; } else { for(int i=1;i<=len1-len2;i++) str2="0"+str2; } len1=str1.length(); int cf=0; int temp; for(int i=len1-1;i>=0;i--) { temp=str1[i]-'0'+str2[i]-'0'+cf; cf=temp/10; temp%=10; str=char(temp+'0')+str; } if(cf!=0) str=char(cf+'0')+str; return str; } //高精度减法 //只能是两个正数相减，而且要大减小 string sub(string str1,string str2)//高精度减法 { string str; int tmp=str1.length()-str2.length(); int cf=0; for(int i=str2.length()-1;i>=0;i--) { if(str1[tmp+i]<str2[i]+cf) { str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str; cf=1; } else { str=char(str1[tmp+i]-str2[i]-cf+'0')+str; cf=0; } } for(int i=tmp-1;i>=0;i--) { if(str1[i]-cf>='0') { str=char(str1[i]-cf)+str; cf=0; } else { str=char(str1[i]-cf+10)+str; cf=1; } } str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0 return str; } //高精度乘法 //只能是两个正数相乘 string mul(string str1,string str2) { string str; int len1=str1.length(); int len2=str2.length(); string tempstr; for(int i=len2-1;i>=0;i--) { tempstr=""; int temp=str2[i]-'0'; int t=0; int cf=0; if(temp!=0) { for(int j=1;j<=len2-1-i;j++) tempstr+="0"; for(int j=len1-1;j>=0;j--) { t=(temp*(str1[j]-'0')+cf)%10; cf=(temp*(str1[j]-'0')+cf)/10; tempstr=char(t+'0')+tempstr; } if(cf!=0) tempstr=char(cf+'0')+tempstr; } str=add(str,tempstr); } str.erase(0,str.find_first_not_of('0')); return str; } //高精度除法 //两个正数相除，商为quotient,余数为residue //需要高精度减法和乘法 void div(string str1,string str2,string "ient,string &residue) { quotient=residue="";//清空 if(str2=="0")//判断除数是否为0 { quotient=residue="ERROR"; return; } if(str1=="0")//判断被除数是否为0 { quotient=residue="0"; return; } int res=compare(str1,str2); if(res<0) { quotient="0"; residue=str1; return; } else if(res==0) { quotient="1"; residue="0"; return; } else { int len1=str1.length(); int len2=str2.length(); string tempstr; tempstr.append(str1,0,len2-1); for(int i=len2-1;i<len1;i++) { tempstr=tempstr+str1[i]; tempstr.erase(0,tempstr.find_first_not_of('0')); if(tempstr.empty()) tempstr="0"; for(char ch='9';ch>='0';ch--)//试商 { string str,tmp; str=str+ch; tmp=mul(str2,str); if(compare(tmp,tempstr)<=0)//试商成功 { quotient=quotient+ch; tempstr=sub(tempstr,tmp); break; } } } residue=tempstr; } quotient.erase(0,quotient.find_first_not_of('0')); if(quotient.empty()) quotient="0"; } int main(){ qc; string n,two="2",one="1",q,r,q1,r1; // cout<<sub(one,one)<<endl; cin>>n; div(n,two,q,r); // dd(r)de(q) if(r=="1") cout<<q; else { div(q,two,q1,r1); // dd(r1)de(q1) if(r1=="1") { if(q==one) cout<<one; else cout<<sub(q,two); } else { if(q==one) cout<<one; else cout<<sub(q,one); } } return 0; }