TCO 2015 Round 1A DIV1
250：
枚举l-r的数，爆搜，统计数位，用map存一下T T
实际上对于每个数小范围暴力即可T T
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int mx=0; map<string,bool> mp; class Similars{ public: void dfs(string a,int x,int tot,bool flag){ if(x==0){ if(flag==1) { if(mp[a])mx=max(mx,tot); } else mp[a]=1; return; } int t=x%10;x/=10; dfs(a,x,tot,flag); a[t]++;if(a[t]=='1')tot++; dfs(a,x,tot,flag); } int maxsim(int L, int R){ string a="0000000000"; for(int i=L;i<=R;i++) { dfs(a,i,0,1); dfs(a,i,0,0); } return mx; } }; |
500：
暴力走min(n^2,K)次，预处理出哪些不能同时取。。。
再暴搜+快速幂算方案TAT
结果有个点T了。。。
正解
假如k步之前在一起了，那么k步的时候一定在一起了
所以如果我们能求出k步的状态，就可以用每个数出现的次数+1的乘积作为答案（可以选择任意数量的放，也可以不放）
所以暴力求状态后乘起来就行了。。。我是SB
暴力
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int mx=0; map<string,bool> mp; class Similars{ public: void dfs(string a,int x,int tot,bool flag){ if(x==0){ if(flag==1) { if(mp[a])mx=max(mx,tot); } else mp[a]=1; return; } int t=x%10;x/=10; dfs(a,x,tot,flag); a[t]++;if(a[t]=='1')tot++; dfs(a,x,tot,flag); } int maxsim(int L, int R){ string a="0000000000"; for(int i=L;i<=R;i++) { dfs(a,i,0,1); dfs(a,i,0,0); } return mx; } }; |
正解。。。其实就是暴力。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; int n;ll ans=1; int to[105],cnt[105]; class Autogame{ public: int wayscnt(vector <int> a, int K){ n=a.size();K=min(K,n*n); for(int i=0;i<n;i++) to[i+1]=a[i]; for(int i=1;i<=n;i++) { int x=i; for(int j=1;j<=K;j++) x=to[x]; cnt[x]++; } for(int i=1;i<=n;i++) ans=(ans*(cnt[i]+1))%mod; printf("%lld",ans); return ans; } }; |
1000
由于不存在完备匹配
根据hall定理
一定存在一个X的子集S，使得S的邻集大小小于S的大小
求出删去邻集每个元素的代价，删最小的几个
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int n,ans=inf; int mp[25][25],v[25]; bool sel[25]; void cal() { memset(v,0,sizeof(v)); int tot=n+1,sum=0; for(int i=1;i<=n;i++) if(sel[i]) { tot--; for(int j=1;j<=n;j++) v[j]+=mp[i][j]; } if(tot>n)return; sort(v+1,v+n+1); for(int i=1;i<=tot;i++) sum+=v[i]; ans=min(ans,sum); } void dfs(int x) { if(x==n+1) { cal(); return; } sel[x]=0; dfs(x+1); sel[x]=1; dfs(x+1); } class Revmatching{ public: int smallest(vector <string> A){ n=A.size(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) mp[i+1][j+1]=A[i][j]-'0'; dfs(1); return ans; } }; |
Subscribe