正題

---

T1:序言頁碼 $PrefaceNumbering$

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1465

---

題目大意

求$1～n$的羅馬數字每個字母出現的次數。

---

解題思路

先寫一個表，表示這個位上出現哪個數字表示$10n$的字母出現次數和表示$5?10n$的字母出現的次數。
然后直接計算

---

code

#include<cstdio> #include<string> using namespace std; const char f[8]={' ','I','V','X','L','C','D','M'}; const int I[11]={0,1,2,3,1,0,1,2,3,1}; const int V[11]={0,0,0,0,1,1,1,1,1,0}; int n,c[8]; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){c[1]+=I[i%10];c[2]+=V[i%10];c[3]+=I[i%100/10]+(i%10==9);c[4]+=V[i%100/10];c[5]+=I[i%1000/100]+(i%100/10==9);c[6]+=V[i%1000/100];c[7]+=I[i/1000]+(i%1000/100==9);}for(int i=1;i<=7;i++)if(c[i]) printf("%c %d\n",f[i],c[i]); }

---

T2:集合 $SubsetSums$

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1466

---

題目大意

求將$1～n$分解為兩組且兩組之和相等的方案數。

---

解題思路

用$f_{i,j}$表示前i個數，兩組相差為j時的方案總數。
然后
$f_{i,j}=f_{i,|j?i|}+f_{i,j+i}$
然后得出的答案要除2，因為兩組是一樣的。

---

code

#include<cstdio> #include<algorithm> #define ll long long using namespace std; ll n,sum,f[40][801]; int main() {scanf("%lld",&n);sum=0;f[0][0]=1;for(ll i=1;i<=n;i++){sum+=i;for(ll j=0;j<=sum;j++){f[i][j]=f[i-1][abs(j-i)]+f[i-1][j+i];}}printf("%lld",f[n][0]/2); }

---

T3:循環數 $RunaroundNumbers$

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1467

---

題目大意

求比n大的第一個循環數（循環數就是每到達一個數字就往前走這個數字的步數，然后每個數字都走過一次）

---

解題思路

直接暴力往后加，然后看一下是不是循環數。

---

code

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,now,k[10],a[10]; bool check(int x) {memset(k,0,sizeof(k));int tmp=x,w=0;while(tmp){w++;a[w]=tmp%10;if(k[a[w]]) return false;k[a[w]]=true;tmp/=10;}for(int i=1;i<=w/2;i++)swap(a[i],a[w-i+1]);memset(k,0,sizeof(k));tmp=1;for(int i=1;i<=w;i++){if(k[a[tmp]]||!a[tmp]) return false;k[a[tmp]]=true;tmp=(tmp+a[tmp]-1)%w+1;}if(tmp!=1) return false;return true; }//判斷循環數 int main() {scanf("%d",&n);now=n;while(true){now++;if(check(now)){printf("%d",now);break;}} }

---

T4:派對燈 $PartyLamps$

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1468

---

題目大意

有n個燈
有4種操作：
1.燈開著就關，關了就開
2.奇數號的取反
3.偶數號的取反
4.3k+1的燈取反
給出操作次數和某些燈的最終狀態，求所有可能的狀態

---

解題思路

我們可以發現其實燈就是6個一個的循環節。
然后一個東西操作過2次就沒有用，然后1和2,3就等于按另一個
我們可以預處理除c=2可以做到的所有情況，然后c>2時也可以做到c=2時的效果

---

code

#include<cstdio> using namespace std; const int s[8]={0,14,21,27,36,42,49,63};//預處理可以做到的情況 int n,c,open,close,a[6],x; bool flag; void check(int x) {if((s[x]&open)!=open||s[x]&close) return;int tmp=s[x],i=1;while(tmp) a[6-i]=tmp%2,tmp/=2,i++;for(int i=0;i<n;i++)printf("%d",a[i%6]);flag=true;printf("\n"); }//判斷這種情況是否滿足 int main() {scanf("%d%d",&n,&c);while(scanf("%d",&x)&&x!=-1)x=6-(x-1)%6-1,open|=1<<x;//開啟的等while(scanf("%d",&x)&&x!=-1)x=6-(x-1)%6-1,close|=1<<x;//關閉的燈if(c==0) check(7);if(c==1) check(0),check(2),check(3),check(5);//前兩個特判if(c>=2) for(int i=0;i<=7;i++) check(i);if(!flag) printf("IMPOSSIBLE"); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的USACO2.2【统计,dp,模拟,位运算】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。