模拟+枚举+模拟……+构造
QAQAQQQ rank12求杯子！
A 顺子
……模拟题，分类讨论一下就好了……比如当前四张牌是不是同一花色……是不是连续的四张牌，如果是连续的四张牌，是不是两边的……（呀我好像忘了判左边。。。只判了J Q K A。。。。没判A 2 3 4。。。aaarticlea/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQH/2wBDAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQH/wAARCAAYABoDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD+u/8AbK/aO134M6JD4J8C+JfBngjx/rnw8+L3xl1T4ifEbQvEfirwD8H/ANnX4ES+BL39oD43674D8OazomufEe68GReP/BPhzwf8NdG17TpvE/jHxNo82ra3aeC7TxdPX5m6L+1bolzB8Srn4n/tf/8ABSr4SfFj4d+A/B/jmLwPqvwo/wCCfEmveM4viFqvwp8IeFfB/wAMvg98Pfgt8btEsfG2t+IfjT8GLHS/gr8abyx+NXhY/En4M6p4xMGm65H4wf6U/bd8CeLNW/a3+HGvaa8F9Yaz8Fr74cWdlDqxi1P+2b34p2+sm3vNIJ2jS9aC6JJ/aF0/lXV/pAjLCS0c18Uat4Y0HxLJ+21qPjz9nn9tP4123wXvfH/wBufix41/al/Yq8A2P7Pvw3+HHxR8P/HXwl4v+DdpZ698H/EngDTv7Z8D/CX48eDPF/i3wL448atpuj/Dd08S6ybLXfDbdlbLKOX5Lk+bzx8FVzuOOTwKlT/d4HB1asPr7lze9Kq4TUIqna0K0aspzXMfA5RxLLM+KuJMipZU/q/Dbypf2h/aHuzzPGzr1J4J5fGCX+w4GPOpLFJpzUuWUleX3d+wB+3xrXx4+K3xg/ZS+M+mahpfx0+DFi3iCCbW9M8B6Tq3xH+Gel+NLj4ceIvEOraN8NvjF8Y/A1j4w+GXxF0jV/h58TLfwZ8QNe8PWHjENo1xJoXxItPiF8KbH9ZtsP8Az7f+Rn/xr8Sv2dfCukwftT/s3fGTxJJ4rk+I/iX4IaAureKvizaeH0+McGkfEn4QaT4u1H4Y/EDXtC8N+FdE1K5XxNa+G72+i8N6Jonh1PGcTaTo3gi0lV5a/cHzZPRv++1/+JrfG5NWyOeFUcc8Rh8xy3BZjhpyS5lTruumuZcnMuaMmnZxakpQlODVR78H8U1OLKOeSw1NZZiMkz3H5HmGESjKMcXgZ8s3H2lRNXvdpd03GMm2/hPx5+zj4j+K/wC0tB4q8bWsqfDXw5beDtS0G60Lxj4i8M+IJte8OXU+uaPFBe+FNb0TXNLuNF8V21rq8phujpWpeH408LavFd6LdazpVer/ABH/AGPf2V/jT4+s/ib8WPgH8M/HvjCxg0S0HiLxR4R0nVJdSsdA1ObV/Dlv4itbiJ7XxPD4V1PF74cHiW0vRoupvJqmiQ2srzzEory8XmGJx9DAxruHLluAyvD4RU4cqhChicSoOV23Kbm3WnJ6zrSlOTblK/Rw3w9gMjqZ7PBzxUpZpnuPzrGSxFf2rnjMRODqJPkjy0FdKFF3SjGEXKUVI8N/ax+BmnXFjqPxJ8AeEdUvPHviXxp4d1DxLrOkz69qutXNlYeE7TwnZQW8DX14+gaFYf8ACP6Hu0jwxaWum2Wpvrvi2VE13UvHutzfYGj3+uvpGlvrjWdhrLadYtq9hb32nT29lqjWyHULSCczkzQ2115sMUpOZERXJJ3ZKK+hjj8TPJsswVSUatHBVcb9WVSCk6ca0MHKcI3dow5qalGEUoqUpys5Nt/HVMjwVDjLifH4eeJw9fNMBw5WxvsKqhCtWp/22o1XFU9JyUrSd2mlFJJpt//Z" alt="" />
没关系加几个字符就好了……嗯代码已改
//hihocoder 12 A
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=1e5+;
/*******************template********************/ bool hv[];
char s[][];
int id1(char ch){
if (ch>='' && ch<='') return ch-'';
if (ch=='A') return ;
if (ch=='J') return ;
if (ch=='Q') return ;
if (ch=='K') return ;
}
int id2(char ch){
if (ch=='S') return ;
if (ch=='H') return ;
if (ch=='C') return ;
if (ch=='D') return ;
}
int main(){
bool sign=;
F(i,,){
scanf("%s",s[i]);
if (s[i][]==''){hv[]=; s[i][]=s[i][];continue;}
hv[id1(s[i][])]=;
if (id1(s[i][])==) hv[]=;
}
F(i,,) if (s[i][]!=s[i-][]) sign=;
F(i,,){
int sum=;
F(j,,) sum+=hv[i+j];
if (sum==){
if (i!= &&i!=){
if (sign) puts("1/6");
else puts("1/8");
}else{
if (sign) puts("1/12");
else puts("1/16");
}
return ;
}
}
F(j,,)
F(i,,){
int sum=;
F(j,,) sum+=hv[i+j];
if (sum==){
if (sign) puts("1/12");
else puts("1/16");
return ;
}
}
puts("0/1");
return ;
}
B 计数
介个……O(n)枚举吧，$10^7$的枚举还是不虚的。
然而这题我又傻逼了……我用的是set插入的，带了log……居然还能过aaarticlea/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQH/2wBDAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQH/wAARCAAYABoDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD+u/8AbK/aO134M6JD4J8C+JfBngjx/rnw8+L3xl1T4ifEbQvEfirwD8H/ANnX4ES+BL39oD43674D8OazomufEe68GReP/BPhzwf8NdG17TpvE/jHxNo82ra3aeC7TxdPX5m6L+1bolzB8Srn4n/tf/8ABSr4SfFj4d+A/B/jmLwPqvwo/wCCfEmveM4viFqvwp8IeFfB/wAMvg98Pfgt8btEsfG2t+IfjT8GLHS/gr8abyx+NXhY/En4M6p4xMGm65H4wf6U/bd8CeLNW/a3+HGvaa8F9Yaz8Fr74cWdlDqxi1P+2b34p2+sm3vNIJ2jS9aC6JJ/aF0/lXV/pAjLCS0c18Uat4Y0HxLJ+21qPjz9nn9tP4123wXvfH/wBufix41/al/Yq8A2P7Pvw3+HHxR8P/HXwl4v+DdpZ698H/EngDTv7Z8D/CX48eDPF/i3wL448atpuj/Dd08S6ybLXfDbdlbLKOX5Lk+bzx8FVzuOOTwKlT/d4HB1asPr7lze9Kq4TUIqna0K0aspzXMfA5RxLLM+KuJMipZU/q/Dbypf2h/aHuzzPGzr1J4J5fGCX+w4GPOpLFJpzUuWUleX3d+wB+3xrXx4+K3xg/ZS+M+mahpfx0+DFi3iCCbW9M8B6Tq3xH+Gel+NLj4ceIvEOraN8NvjF8Y/A1j4w+GXxF0jV/h58TLfwZ8QNe8PWHjENo1xJoXxItPiF8KbH9ZtsP8Az7f+Rn/xr8Sv2dfCukwftT/s3fGTxJJ4rk+I/iX4IaAureKvizaeH0+McGkfEn4QaT4u1H4Y/EDXtC8N+FdE1K5XxNa+G72+i8N6Jonh1PGcTaTo3gi0lV5a/cHzZPRv++1/+JrfG5NWyOeFUcc8Rh8xy3BZjhpyS5lTruumuZcnMuaMmnZxakpQlODVR78H8U1OLKOeSw1NZZiMkz3H5HmGESjKMcXgZ8s3H2lRNXvdpd03GMm2/hPx5+zj4j+K/wC0tB4q8bWsqfDXw5beDtS0G60Lxj4i8M+IJte8OXU+uaPFBe+FNb0TXNLuNF8V21rq8phujpWpeH408LavFd6LdazpVer/ABH/AGPf2V/jT4+s/ib8WPgH8M/HvjCxg0S0HiLxR4R0nVJdSsdA1ObV/Dlv4itbiJ7XxPD4V1PF74cHiW0vRoupvJqmiQ2srzzEory8XmGJx9DAxruHLluAyvD4RU4cqhChicSoOV23Kbm3WnJ6zrSlOTblK/Rw3w9gMjqZ7PBzxUpZpnuPzrGSxFf2rnjMRODqJPkjy0FdKFF3SjGEXKUVI8N/ax+BmnXFjqPxJ8AeEdUvPHviXxp4d1DxLrOkz69qutXNlYeE7TwnZQW8DX14+gaFYf8ACP6Hu0jwxaWum2Wpvrvi2VE13UvHutzfYGj3+uvpGlvrjWdhrLadYtq9hb32nT29lqjWyHULSCczkzQ2115sMUpOZERXJJ3ZKK+hjj8TPJsswVSUatHBVcb9WVSCk6ca0MHKcI3dow5qalGEUoqUpys5Nt/HVMjwVDjLifH4eeJw9fNMBw5WxvsKqhCtWp/22o1XFU9JyUrSd2mlFJJpt//Z" alt="" />（可能是满足条件的点太少？其实是数据太弱。。。？
//hihocoder 12 B
#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=1e5+;
/*******************template********************/ LL n,L,R;
set<LL>s; int main(){
n=getint(); L=getint(); R=getint();
F(i,,){
LL t=i^(n*i);
if (t>=L && t<=R) s.insert(t);
}
printf("%d\n",s.size());
return ;
}
C 永恒游戏
神题，蒟蒻并不会做……经过大胆猜想，不用(hui)证明，yy了一个做法：每次找度数最小的可操作点进行操作，然后模拟10W次……居然就过了……过了……了……
题解说：
有一个定理保证，对于一个固定的初始局面，不论怎么操作，要么可以无限操作下去，要么在相同步数之后停在相同的局面上。所以只需要模拟100000次即可知道本题答案。
定理的证明可以在以下论文中找到 http://www.cs.elte.hu/~lovasz/morepapers/chips.pdf （定理1.1）
E文的paper差评QAQ，蒟蒻太傻逼看不懂啊QAQ
//hihocoder 12 C
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/ int n,m,a[N][N],du[N],num[N];
int main(){
n=getint(); m=getint();
F(i,,n) num[i]=getint();
F(i,,m){
int x=getint()+,y=getint()+;
a[x][y]=a[y][x]=;
du[x]++; du[y]++;
}
F(i,,){
int mn=,t=-;
F(j,,n)
if (num[j]>=du[j])
if (du[j]<mn) mn=du[j],t=j;
if (t==-){
printf("%d\n",i-); return ;
}
F(j,,n){
if (a[t][j]) num[j]++,num[t]--;
}
}
puts("INF");
return ;
}
D 天下无骰
神一样的构造题……
然而我连题都没读对aaarticlea/jpeg;base64,/9j/4AAQSkZJRgABAQEASABIAAD/2wBDABsSFBcUERsXFhceHBsgKEIrKCUlKFE6PTBCYFVlZF9VXVtqeJmBanGQc1tdhbWGkJ6jq62rZ4C8ybqmx5moq6T/2wBDARweHigjKE4rK06kbl1upKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKT/wAARCAA0ADgDASIAAhEBAxEB/8QAGgAAAgMBAQAAAAAAAAAAAAAAAAUCAwQGAf/EAC4QAAIBAwMDAwMCBwAAAAAAAAECAwAEEQUSIRMiMUFRYRUycQYUI1JygZHB0f/EABQBAQAAAAAAAAAAAAAAAAAAAAD/xAAUEQEAAAAAAAAAAAAAAAAAAAAA/9oADAMBAAIRAxEAPwBtqeomzMcUUfVnlOESsX1TULNt2oWgEJ8vH6VKbB/VMIfx0jtz7006XVheOdchsgg88UEoJo7iJZYmDI3gira50aQNPj3NqE6JnACcZrPHNdxnNjdSyc/ZNj/tB1VFJLTWZQdl7AUI8lR4/Iq+61u0gO1d8reoQZoGdFYtP1S21AERMQ48o3migwpE1/r7zEkRWhCj5b1p3Sr9NqfpvUb75HZiffmmjEKMk4AoEeqNNLfCNo3MQ+1VbaSR61VDA8qtEf4nH2TJscfg00vujNGrMAoB4kJxtquGWS2nihmdZkk4jk9fxQUx2M5AjlYsMZjlI70PsferNPk6DvbSwKlwBuyvhx8U0rJeWonkjZSySKeHUeB60GC6jj+t2JjUJOdxk2+3zRVeipu1a8aaQyyxnarn2ooLtKf9leT6dKQO4yQ/INM5xvjdAeceKXPpkt2iTXMpW5XlCPCV7DdXtp23sJlUcdWIZP8AcUFNtcXU0ARlt50Pa8QPcKjNbiERvDJLiBg4icenxUhaadfOZlUh2Od8bYOatt9Pusskl27W/oHGW/zQNIpFljV0OVYZFErbY3YDJAJpdCzWFx0iM28jdhGe0+1MiNy4x5oFOlYNwjgdzw5fAxzmivNGikt725glGNo7P6c0UDiiiigx3GnWsxaQxhJMZ3pwaXTzXFrlUuZGA/nwf9UUUGB9SurhJI5JO3g8ADFdVGcxqfiiigyXHbqVqw4LBlPyMUUUUH//2Q==" alt="" />
其实是：决策树上的叶子可以有很多，而且可以多个叶子标相同的号，只要保证标同一个号的叶子的概率之和为$\frac{1}{n}$即可……
然而如果是必须要只能一个叶子呢？我yy的做法是这样的：（口胡时间√）
首先我们一定要有一个$\frac{1}{2}$的硬币……因为最后两个叶子之间的概率必然得相等……
然后我们现在就可以处理n是2的幂的情况了
然后我们考虑另一个硬币可以做什么？可以将不是2的幂的情况，比如5，变成2的幂的和（1+4）然而只能分出来两个……所以是二进制表示中1的数量=2的才可以……
然而这并不是本题正解233只是感觉这个思路很有趣不想让它就这么消失……说不定哪天我可以出一道题（大雾）？2333。。。。
至于正解。。。太麻烦了蒟蒻看不懂QAQ
//hihocoder 12 D
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=5e5+;
/*******************template********************/ int n,m,v[N],c[N][],tot,a[N],num,p0,q0,p1,q1;
bool sign[N]; void dfs(int x,int a){
if (a==){
sign[x]=;
return;
}
if (a%q0==){
v[x]=;
c[x][]=++tot;
c[x][]=++tot;
dfs(c[x][],a/q0*p0);
dfs(c[x][],a/q0*(q0-p0));
return;
}
if (a%q1==){
v[x]=;
c[x][]=++tot;
c[x][]=++tot;
dfs(c[x][],a/q1*p1);
dfs(c[x][],a/q1*(q1-p1));
return;
}
}
void work(){
puts("YES");
printf("%d %d %d %d\n",p0,q0,p1,q1);
dfs(,n);
int num=;
printf("%d\n",tot+);
F(i,,tot-){
if (sign[i]){ printf("E %d\n",num++); continue;}
printf("C %d %d %d\n",v[i],c[i][],c[i][]);
}
printf("E %d",num++);
} int cnt(int x){
int ans=;
while(x){
ans+=x&;
x>>=;
}
return ans;
}
int main(){
m=n=getint();
F(i,,n){
if (cnt(i)<=) a[++num]=i;
}
while((m&)==) m>>=;
while(m%==) m/=;
p1=,q1=;
if (m==){
p0=,q0=;
work();
return ;
}
F(i,,num){
m=n;
while((m&)==) m>>=;
while(m%a[i]==) m/=a[i];
if (m==){
q0=a[i];
p0=a[i]&(-a[i]);
work();
return ;
}
}
puts("NO");
return ;
}
（WA）