ZOJ-3956-Course Selection System

2023-08-30T16:19:00+08:00

Problem DescriptionThere are $n$ courses in the course selection system of Marjar University. The $i$-th course is described by two values: happiness $Hi$ and credit $Ci$. If a student selects $m$ courses $x1$, $x2$, ..., $xm$, then his comfort level of the semester can be defined as follows:$$(\sum^m_{i=1}H_{x_i})^2-(\sum^m_{i=1}H_{x_i})\times (\sum^m_{i=1}C_{x_i})-(\sum^m_{i=1}C_{x_i})^2$$Edward, a student in Marjar University, wants to select some courses (also he can select no courses, then his comfort level is $0$) to maximize his comfort level. Can you help him?InputThere are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:The first line contains a integer $n$ $(1 ≤ n ≤ 500)$ -- the number of cources.Each of the next $n$ lines contains two integers $H_i$ and $C_i$ $(1 ≤ H_i ≤ 10000, 1 ≤ C_i ≤ 100)$.It is guaranteed that the sum of all $n$ does not exceed $5000$.We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.OutputFor each case, you should output one integer denoting the maximum comfort.Sample Input2 3 10 1 5 1 2 10 2 1 10 2 10Sample Output191 0HintFor the first case, Edward should select the first and second courses.For the second case, Edward should select no courses.Problem Link[button color="success" url="https://vjudge.net/problem/ZOJ-3956" outline="default" target="_blank"]vjudge_ZOJ-3956-Course Selection System[/button]Thought通过题目我们可以了解到在一定的$C$下$H$越高，$comfort level$就越高，所以我们应该求出在所有可能的$C$值下最高的$H$值，因为$C$的最大值并不大，题目给出不超过$5000$；因此我们可以创建一个数组来进行0/1背包的求解。求出每个$C$下最高的$H$，注意$H$的范围，所以int的范围是不够表达comfortable的值的，要用long long int,求出所有最高$H$后再进行计算，求出所有$C$中的最优解。Code#include #include #include #include # define MaxN 500+5 # define MaxC 500*100+5 typedef long long int LL; LL max(LL a,LL b) { return a>b ? a:b; } int main() { int T; scanf("%d",&T); while(T--) { int dp[MaxC]; int H[MaxN]; int C[MaxN]; memset(dp,0,sizeof dp); int N; int i; int TopC=0; scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%d",&H[i]); scanf("%d",&C[i]); TopC+=C[i]; } for(i=1;i<=N;i++) { int l; for(l=TopC;l>=C[i];--l) dp[l]=max(dp[l],dp[l-C[i]]+H[i]); } LL max1=0; for(i=0;i<=TopC;i++) max1=max(1LL*dp[i]*dp[i]-1LL*dp[i]*i-1LL*i*i,max1); printf("%lld",max1); if(T!=0) printf("\n"); } return 0; }

ZOJ_3961_Let's Chat

2023-08-30T13:22:00+08:00

Problem DescriptionACM (ACMers' Chatting Messenger) is a famous instant messaging software developed by Marjar Technology Company. To attract more users, Edward, the boss of Marjar Company, has recently added a new feature to the software. The new feature can be described as follows:If two users, $A$ and $B$, have been sending messages to each other on the last m consecutive days, the "friendship point" between them will be increased by $1$ point.More formally, if user A sent messages to user B on each day between the $(i - m + 1)$-th day and the $i$-th day (both inclusive), and user $B$ also sent messages to user $A$ on each day between the $(i - m + 1)$-th day and the $i$-th day (also both inclusive), the "friendship point" between $A$ and $B$ will be increased by $1$ at the end of the i-th day.Given the chatting logs of two users $A$ and $B$ during $n$ consecutive days, what's the number of the friendship points between them at the end of the $n$-th day (given that the initial friendship point between them is $0$)?InputThere are multiple test cases. The first line of input contains an integer $T$ $(1 ≤ T ≤ 10)$, indicating the number of test cases. For each test case:The first line contains $4$ integers $n$ $(1 ≤ n ≤ 10^9)$, $m$ $(1 ≤ m ≤ n)$,$x$ and $y$ $(1 ≤ x, y ≤ 100)$. The meanings of $n$ and $m$ are described above, while $x$ indicates the number of chatting logs about the messages sent by $A$ to $B$, and $y$ indicates the number of chatting logs about the messages sent by $B$ to $A$.For the following $x$ lines, the $i$-th line contains $2$ integers $l_{a, i}$ and $r_{a, i} (1 ≤ l_{a, i} ≤ r_{a, i} ≤ n)$, indicating that $A$ sent messages to $B$ on each day between the $l_{a, i}$-th day and the $r_{a, i}$-th day (both inclusive).For the following $y$ lines, the $i$-th line contains $2$ integers $l_{b, i}$ and $r_{b, i} (1 ≤ l_{b, i} ≤ r_{b, i} ≤ n)$, indicating that $B$ sent messages to $A$ on each day between the $l_{b, i}$-th day and the $r_{b, i}$-th day (both inclusive).It is guaranteed that for all $1 ≤ i < x$, $r_{a, i} + 1 < l_{a, i+1} $ and for all $1 ≤ i < y, r_{b, i} + 1 < l_{b, i + 1}$.OutputFor each test case, output one line containing one integer, indicating the number of friendship points between $A$ and $B$ at the end of the $n$-th day.Sample Input2 10 3 3 2 1 3 5 8 10 10 1 8 10 10 5 3 1 1 1 2 4 5Sample Output3 0HintFor the first test case, user $A$ and user $B$ send messages to each other on the $1st$, $2nd$, $3rd$, $5th$, $6th$, $7th$, $8th$ and $10th$ day. As $m = 3$, the friendship points between them will be increased by $1$ at the end of the $3rd$, $7th$ and $8th$ day. So the answer is $3$.Problem Link[button color="success" url="https://vjudge.net/problem/ZOJ-3962" outline="default" target="_blank"]vjudge_ZOJ-3961-Let's Chat[/button]Thoughts一个求交集的问题，把区间表示出来就好Code#include #include #include #include #define MAX 100+10 typedef long long LL; struct cbc { LL l,r; }AtoB[MAX],BtoA[MAX]; LL max(LL a,LL b) { return a>b ? a:b; } LL min (LL a,LL b) { return ar || r-l+1

ZOJ_3962_Seven Segment Display

2023-08-30T00:01:00+08:00

Problem DescriptionA seven segment display, or seven segment indicator, is a form of electronic display device for displaying decimal numerals that is an alternative to the more complex dot matrix displays. Seven segment displays are widely used in digital clocks, electronic meters, basic calculators, and other electronic devices that display numerical information.Edward, a student in Marjar University, is studying the course "Logic and Computer Design Fundamentals" this semester. He bought an eight-digit seven segment display component to make a hexadecimal counter for his course project.In order to display a hexadecimal number, the seven segment display component needs to consume some electrical energy. The total energy cost for display a hexadecimal number on the component is the sum of the energy cost for displaying each digit of the number. Edward found the following table on the Internet, which describes the energy cost for display each kind of digit. 　　　　　　　For example, in order to display the hexadecimal number "$5A8BEF67$" on the component for one second, $5 + 6 + 7 + 5 + 5 + 4 + 6 + 3 = 41$ units of energy will be consumed.Edward's hexadecimal counter works as follows:The counter will only work for n seconds. After $n$ seconds the counter will stop displaying.At the beginning of the 1st second, the counter will begin to display a previously configured eight-digit hexadecimal number $m$.At the end of the $i$-th second ($1$ $≤$ $i$ $<$ $n$), the number displayed will be increased by $1$. If the number displayed will be larger than the hexadecimal number "$FFFFFFFF$" after increasing, the counter will set the number to $0$ and continue displaying.InputThere are multiple test cases. The first line of input contains an integer $T$ $(1 ≤ T ≤ 10^5)$, indicating the number of test cases. For each test case:The first and only line contains an integer $n (1 ≤ n ≤ 10^9)$ and a capitalized eight-digit hexadecimal number $m (00000000 ≤ m ≤ FFFFFFFF)$, their meanings are described above.We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.OutputFor each test case output one line, indicating the total units of energy consumed by the eight-digit seven segment display component.Sample Input3 5 89ABCDEF 3 FFFFFFFF 7 00000000Sample Output208 124 327HintFor the first test case, the counter will display $5$ hexadecimal numbers $(89ABCDEF, 89ABCDF0, 89ABCDF1, 89ABCDF2, 89ABCDF3)$ in $5$ seconds. The total units of energy cost is $$\begin{align}(7 + 6 + 6 + 5 + 4 + 5 + 5 + 4) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 6) \\ + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 2) + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) \\ + (7 + 6 + 6 + 5 + 4 + 5 + 4 + 5) = 208\end{align}$$.For the second test case, the counter will display $3$ hexadecimal numbers $(FFFFFFFF, 00000000, 00000001)$ in $3$ seconds. The total units of energy cost is $$\begin{align}(4 + 4 + 4 + 4 + 4 + 4 + 4 + 4) + (6 + 6 + 6 + 6 + 6 + 6 + 6 + 6) \\ + (6 + 6 + 6 + 6 + 6 + 6 + 6 + 2) = 124\end{align}$$.Problem Link[button color="success" url="https://vjudge.net/problem/ZOJ-3962" outline="default" target="_blank"]vjudge_ZOJ_3962_Seven Segment Display[/button]Thoughts数位DP，有点像打表的感觉，但又没那么容易，首先判断一下$n$秒以后有没有超过$0xffffffff$如果超了，那么结果就等于$\begin{align}(0xffffffff的权值-((初始值-1的权值)- (初始值加上n-1秒-(0xffffffff+1)后的权值)))\end{align}$若没超过那就好算了$(初始值+n-1的权值-初始值-1的权值)$没看懂的可以自己画个图试一下，就是如果超过了$0xffffffff$就求补集否则，直接求。Code#include #include #include #include typedef long long LL; int cost[16]={6,2,5,5,4,5,6,3,7,6,6,5,4,5,5,4}; const LL mod =(LL)0xffffffff+1; int a[20]; //存储16进制数字（字母转化为数字） LL dp[20][1005]; //数位dp，名字不用管啦，看代码就知道了 LL change(char *str) //将字符串组合成一个16进制的数 { LL tmp=0; for(int i=0;i<8;i++) { if(str[i]>='0' && str[i]<='9') tmp=tmp*16+str[i]-'0'; else tmp=tmp*16+str[i]-'A'+10; } return tmp; } LL dfs(int pos, LL sum,int limit) { if(pos<0) //若最低位已经计算完成 return sum; if(!limit && dp[pos][sum]!=-1) //效率优化，极大极大的优化的 return dp[pos][sum]; int up=limit ? a[pos]:15; LL tmp=0; for(int i=0;i<=up;i++) //计算此位上所有可能的数字的权值和，类似打表 tmp+=dfs(pos-1,sum+cost[i],limit&&(i==a[pos])); if(!limit ) dp[pos][sum]=tmp; //记录可能会重复利用的数字 return tmp; } LL solve(LL x)//将整个16进制数各个位数拆分 { int pos=0; memset(a,0,sizeof(a)); //因为有多组数据，计算前先清空之前计算过的数据 while(x) { a[pos++]=x%16; x/=16; } return dfs(7,0,1); //由于数组中各个位数排序位置与大数相反，所以最高位为下标为7的时候 } int main() { int T; scanf("%d",&T); memset(dp,-1,sizeof(dp)); while(T--) { int setp; char str[20]; scanf("%d %s",&setp,str); setp--; LL l=change(str); //将16进制字符转换为10进制数字 LL b=setp/mod; //每从0x00000000到0xffffffff是一个循环节，超过的用倍数统计即可 if(l+setp>=mod) { LL r=(l+setp)%mod; printf("%lld\n",(b+1)*solve((LL)0xffffffff)-(solve(l-1)-solve(r))); } else { LL r=l+setp; printf("%lld\n",solve(r)-solve(l-1)); } } return 0; }

HDU_2089_不要62

2023-08-29T23:50:00+08:00

问题描述杭州人称那些傻乎乎粘嗒嗒的人为$62$（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如：$62315$ $73418$ $88914$都属于不吉利号码。但是，$61152$虽然含有$6$和$2$，但不是$62$连号，所以不属于不吉利数字之列。你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。输入输入的都是整数对$n$、$m$$(0 #include #include #include typedef long long LL; int a[10]; int dp[10][3]; //只需记录三种状态，分析里有解释 LL dfs(int last,int pos,int limit,int symbol) { if(symbol==1 && !limit) return pow(10,pos); if(pos<1) if(symbol==1) return 1; else return 0; if(!limit) { if(symbol==1 && dp[pos][0]!=-1) return dp[pos][0]; if(symbol==0 && last==6 && dp[pos][1]!=-1) return dp[pos][1]; if(symbol==0 && last != 6 && dp[pos][2]!=-1) return dp[pos][2]; } int up=limit ? a[pos]:9; int i; LL tmp=0; for(i=0;i<=up;i++) tmp+=dfs(i,pos-1,limit && i==a[pos],(i==4 ||(last==6 && i==2)) || symbol); if(!limit) { if(symbol==1 && dp[pos][0]!=-1) dp[pos][0]=tmp; if(symbol==0 && last==6 && dp[pos][1]!=-1) dp[pos][1]=tmp; if(symbol==0 && last != 6 && dp[pos][2]!=-1) dp[pos][2]=tmp; } return tmp; } LL solve(LL x) { memset(a,-1,sizeof(a)); int a_=1; while(x>0) { a[a_++]=x%10; x/=10; } return dfs(0,a_-1,1,0); } int main() { LL n,m; memset(dp,-1,sizeof(dp)); while(scanf("%lld%lld",&n,&m)!=EOF) { if(n==0 && m==0) break; printf("%lld\n",m-n+1-(solve(m)-solve(n-1))); } return 0; }

2018计蒜之道初赛第一场百度科学家（中等）

2023-08-28T23:42:00+08:00

题目描述百度有一位非常有名的大科学家，这位大科学家有很多藏书。大科学家有一个图书馆，所以放书的容量也随之增加了，图书馆可以看成一个长度为$N$的序列，一开始里面放着 $N$ 本书，每本书都记载了一个特定元素的信息，书中的元素各不相同。大科学家会先进行若干次研究，最后进行一次科学实验，这次实验需要选取一些元素放在一起来进行。每次研究，大科学家会从图书馆中的某些位置抽出一些书来看，然后得出“如果$x$位置上的书对应的元素被拿来做实验了，那么区间$[l,r]$位置上的书对应的元素也必须拿来做实验，否则会爆炸”这样的结论。大科学家有不止$N$本书（也就是说世界上有不止$N$种元素），但是他自己没时间给图书馆换书，所以他雇了一个实习生，这个实习生会时不时地拿出一本从来没被放入图书馆的书，然后替换掉图书馆中某个位置原来的书（所以对于大科学家得到的两次看似一样的研究结果，可能由于图书馆中的书被换了，它们的实质内容可能不一样）。每本书还记载着对应元素的非负污染值，大科学家希望在完成一次科学实验的前提下（不能不选任何元素），这次实验的总污染值最小。作为一个旁观者，你能看到科学家做的所有研究结果以及实习生换书的顺序，然后你需要告诉大科学家，这个最小总污染值是多少。由于大科学家精力有限，所以它只能得出不多的实验结论（具体参见数据范围）。输入格式第一行一个正整数 $N$，代表图书馆的容量。接下来一行 $N$ 个数，第 $i$ 个非负整数 $a_i$ 代表最开始图书馆中第 $i$ 本书所描述的元素的污染值。接下来一行一个整数 $M$，代表事件的总数。接下来 $M$ 行，每行代表一个事件：若为 $0$ $x$ $y$，代表实习生拿了一本新书替换了 $x$ 位置的书，新书对应元素的污染值为 $y$。若为 $1$ $x$ $l$ $r$，代表大科学家得到了新的结果，如果 $x$ 位置的书对应的元素加入了实验，那么 $[l,r]$ 区间内的书对应的元素都必须拿来做实验。保证大科学家的书籍总数$(N+ 新书数量)\le 10^5$。每个元素的污染值 $0\le (a_i,y)\le 10^9$。保证 $1\le x\le N$，$1 \le l \le r \le N$，$M \le 10^5$。由于大科学家的精力有限，做不了太多的实验，所以我们保证 $\sum(r-l+1) \le 10^5$。输出格式输出一个整数，代表最小总污染值。样例解释一开始书架上有 $5$ 本书，我们记这些元素的编号顺次为 $1$,$2$,$3$,$4$,$5$，他们的污染值分别为 $1$,$10$,$100$,$1000$,$10000$。一共有 $4$ 个事件：大科学家发现，选了元素 $1$ 就必须选元素 $3$,$4$。大科学家发现，选了元素 $3$ 就必须选元素 $5$。实习生拿了一本新书，我们记这个新元素的编号为 $6$，他的污染值为 $0$，替换掉现在书架上的第 $3$ 本书，现在书架上的 $5$ 本书对应元素为 $1$,$2$,$6$,$4$,$5$。大科学家发现，选了元素 $6$（因为它在位置 $3$ 上）就必须选元素 $1$,$2$。于是在所有可能的方案中，单选一个元素 $2$ 来做实验是总污染值最小的，因为如果选择元素 $1$ 或元素 $6$，都存在一些绑定关系使得总污染值不可能比 $10$ 更小。样例输入5 1 10 100 1000 10000 4 1 1 3 4 1 3 5 5 0 3 0 1 3 1 2样例输出10题目链接[button color="success" url="https://vjudge.net/problem/计蒜客-A1691" outline="default" target="_blank"]👉vjudge_计蒜客-A1691[/button]思路看成有向图的话不难发现答案一定在出度为$0$的子图里，只是环比较难以解决，$tarjan$缩点算法可以有效计算强连通分量，即缩圈成点，蓝书上有介绍，强连通分量。代码#include #include #include #include #include #include #include #define MaxN 100000+100 typedef long long LL; using namespace std; const LL inf=1e15+7; LL value[MaxN]; int book[MaxN]; vectorG[MaxN]; stackSta; stackcopy; int pre[MaxN]; int low_link[MaxN]; int scc[MaxN]; int dfs_cnt,scc_cnt; LL result=inf; void dfs(int now) { low_link[now]=pre[now]=++dfs_cnt; Sta.push(now); for(int i=0;i

2018计算之道初赛第二场阿里巴巴的手机代理商（中等）

2023-08-28T23:08:00+08:00

题目描述阿里巴巴的手机代理商正在研究 infra 输入法的新功能。他们需要分析单词频率以改进用户输入法的体验。于是需要你在系统内核里面写一个 API。API有如下功能：添加操作添加操作格式为$insert~~barty~~8$，意思为插入$barty$这个单词，这个单词词频为 $8$ 次。注意如果再次添加$insert~~barty~~8$操作时，就会将词频增加为 $16$ 次。（不会出现词频$\le 0$的情况）。删除操作删除操作格式为$delete~~barty$，意思为删除所有$barty$这个单词。如果当前没有删除的词汇，输出"$Empty$"。查询操作查询操作格式为$query~~ty$，意思为查询当前版本以$ty$结尾的单词词频总和。修改操作修改操作格式为$update~~ty~~tied$，意思为将所有结尾是$ty$的单词更新为$tied$结尾，比如$barty$会变为$bartied$。如果不存在$ty$结尾的单词，输出$Empty$。如果已经存在$tied$结尾的单词，那么说明存在$conflict$。不做合并，输出$Conflict$。如果既不存在$ty$结尾的单词，也已经存在以$tied$结尾的单词，则输出$Empty$。输入格式第一行读入一个整数 $T$，代表数据组数。每组数据的第一行读入一个整数 $N$ 代表操作数。接下来 $N$ 行，每行形容一个操作。保证数据满足 $1\le T\le 10$，$1\le N\le 10^5$，$insert$和$update$操作的字符串总长度之和 $\le 10^6$，所有字符串长度 $≤10^6$，输入只有小写字母。输出格式输出题目中要求的结果样例输入1 10 update y ty insert barty 8 delete shawn update ty tied query tied insert party 9 update y tied query ty delete barty query tied样例输出Empty Empty 8 Conflict 9 Empty 8题目链接[button color="success" url="https://vjudge.net/problem/计蒜客-A1703" outline="default" target="_blank"]👉vjudge_阿里巴巴的手机代理商（中等）[/button] [quote color="info"]注:登陆了才能看到题目[/quote]思路逆序字典树，转移的时候把所有节点都移过去的ok了，这样每个操作效率是$O(n*26),n<10^6$。代码#include #include #include #include typedef long long LL; struct trie { LL count; trie *next[26]; }; trie *root; trie* newtrie() { trie *t; t=(trie*)malloc(sizeof(struct trie)); memset(t,0,sizeof(struct trie)); return t; } char oo[100000+100]; char o2[100000+100]; void Insert(char *ch,LL num) { int i; trie *t,*s; s=root; for(i=0;ch[i];i++) { if(s->next[ch[i]-'a']) { s=s->next[ch[i]-'a']; s->count=s->count+num; } else { t=newtrie(); s->next[ch[i]-'a']=t; s=t; s->count=num; } } } LL Search(char *ch)/*搜索函数，返回0则代表字典树不存在该字符串，反之亦然 */ { int i; trie *s=root; if(ch[0]==0) return 0; for(i=0;ch[i];i++) { if(s->next[ch[i]-'a']) s=s->next[ch[i]-'a']; else break; } if(ch[i]==0) return s->count; else return 0; } bool Delete(char *ch)/*删除函数，将该字符串从字典树中删除（删除之前记得事先判断存不存在该字符串）*/ { int i; trie *s; s=root; if(ch[0]==0) return false; for(i=0;ch[i];i++) { // printf("%c -%lld\n",ch[i],s->count); if(s->next[ch[i]-'a']) s=s->next[ch[i]-'a']; else return false; } LL sum=0; sum+=s->count; for(i=0;i<26;i++) if(s->next[i]) sum-=s->next[i]->count; if(sum==0) return false; Insert(ch,-sum); return true; } LL Update(char *ch1,char *ch2) { LL t1,t2; t1=Search(ch1); t2=Search(ch2); if(t1==0) return -1;//printf("%d %d\n",t1,t2); if(t2!=0) return 1; // int i; trie *t,*s; s=root; for(i=0;ch1[i];i++) s=s->next[ch1[i]-'a']; trie *pp[26]; LL sum=s->count; for(i=0;i<26;i++) { pp[i]=s->next[i]; s->next[i]=NULL; } Insert(ch1,-sum); s=root; // for(i=0;ch2[i];i++) { if(s->next[ch2[i]-'a']) { s=s->next[ch2[i]-'a']; s->count+=sum; } else { t=newtrie(); s->next[ch2[i]-'a']=t; s=t; s->count=sum; } } for(int i=0;i<26;i++) s->next[i]=pp[i]; return 0; // } void swap(char *ch) { int len=strlen(ch); for(int i=0;inext[i]); free(now); } int main() { int T; scanf("%d",&T); root=newtrie(); while(T--) { int N; scanf("%d",&N); clear(root); root=newtrie(); while(N--) { char ope[10]; getchar(); scanf("%s",ope); if(ope[0]=='i') { LL tt; scanf("%s %lld",oo,&tt); swap(oo); Insert(oo,tt); } if(ope[0]=='d') { scanf("%s",oo); swap(oo); bool q=Delete(oo); if(q==false) printf("Empty\n"); } if(ope[0]=='q') { scanf("%s",oo); swap(oo); LL z=Search(oo); if(z==0) printf("0\n"); else printf("%lld\n",z); } if(ope[0]=='u') { scanf("%s %s",oo,o2); swap(oo); swap(o2); int z=Update(oo,o2); if(z==-1) printf("Empty\n"); if(z==1) printf("Conflict\n"); // printf("\n\n%d\n\n",z); } } } return 0; }

ural1519 Formula 1

2023-08-28T22:16:00+08:00

BackgroundRegardless of the fact, that Vologda could not get rights to hold the Winter Olympic games of 20**, it is well-known, that the city will conduct one of the Formula 1 events. Surely, for such an important thing a new race circuit should be built as well as hotels, restaurants, international airport - everything for Formula 1 fans, who will flood the city soon. But when all the hotels and a half of the restaurants were built, it appeared, that at the site for the future circuit a lot of gophers lived in their holes. Since we like animals very much, ecologists will never allow to build the race circuit over the holes. So now the mayor is sitting sadly in his office and looking at the map of the circuit with all the holes plotted on it.ProblemWho will be smart enough to draw a plan of the circuit and keep the city from inevitable disgrace? Of course, only true professionals - battle-hardened programmers from the first team of local technical university!.. But our heroes were not looking for easy life and set much more difficult problem: "Certainly, our mayor will be glad, if we find how many ways of building the circuit are there!" - they said.It should be said, that the circuit in Vologda is going to be rather simple. It will be a rectangle $N* M$ cells in size with a single circuit segment built through each cell. Each segment should be parallel to one of rectangle's sides, so only right-angled bends may be on the circuit. At the picture below two samples are given for $N = M = 4$ (gray squares mean gopher holes, and the bold black line means the race circuit). There are no other ways to build the circuit here. 　　　　　　　　　　　　　　　　InputThe first line contains the integer numbers $N$ and $M (2 ≤ N, M ≤ 12)$. Each of the next $N$ lines contains $M$ characters, which are the corresponding cells of the rectangle. Character "$.$" (full stop) means a cell, where a segment of the race circuit should be built, and character "$*$" (asterisk) - a cell, where a gopher hole is located. There are at least $4$ cells without gopher holes.OutputYou should output the desired number of ways. It is guaranteed, that it does not exceed $2^{63}-1$.Sample InputSample14 4 **.. .... .... ....Sample24 4 .... .... .... ....Sample OutputSample12Sample26Translation有一个$n\times m$的棋盘，'$.$'能走，'*'不能走，请问有多少种不同的走法能够经过所有点并且每个每个点不重复并且路径形成一个回路，即有多少个哈密顿回路。Problem Link[button color="success" url="https://vjudge.net/problem/URAL-1519" outline="default" target="_blank"]👉vjudge-ural_1519_Formula 1[/button]Thoughtskuangbin系列插头dp入门题。佩服cdq大佬高中就能够想出这种算法。#include #include #include #include #include #include using namespace std; typedef long long ll ; ll a[1594323+10]; ll newa[1594323+10]; char mg[15][15]; queueQQ[2]; bool flag[1594323+10]; int my_min(int a,int b) { return a

PTA_L3-011_直捣黄龙

2023-08-27T23:25:00+08:00
描述本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。输入格式输入第一行给出$2$个正整数$N$ $(2 \le N \le 200，城镇总数)$和$K(城镇间道路条数)$，以及己方大本营和敌方大本营的代号。随后$N-1$行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有$K$行，每行按格式$城镇1$ $城镇2$ 距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由$3$个大写英文字母组成的字符串。输出格式按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式$己方大本营\rightarrow 城镇1->...->敌方大本营$输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以$1$个空格分隔，行首尾不得有多余空格。输入样例10 12 PAT DBY DBY 100 PTA 20 PDS 90 PMS 40 TAP 50 ATP 200 LNN 80 LAO 30 LON 70 PAT PTA 10 PAT PMS 10 PAT ATP 20 PAT LNN 10 LNN LAO 10 LAO LON 10 LON DBY 10 PMS TAP 10 TAP DBY 10 DBY PDS 10 PDS PTA 10 DBY ATP 10输出样例PAT->PTA->PDS->DBY 3 30 210思路枚举各种路线的走法，然后把满足条件的路线和最优路线给记录下来。由于要考虑每一条路线，即把每一条路线都给走一遍，所以我们需要回溯题目链接[button color="success" url="https://pintia.cn/problem-sets/994805046380707840/problems/994805049455132672" outline="default" target="_blank"]👉PTA_L3-011_直捣黄龙[/button]代码#include #include struct cityi //城市数据 { int arrive_; //可以进入的城市的数目 struct a { int cityid; //可以进入的城市 int distance; //去这个城市所需要的距离 }arrive[199+20]; //由于城市上限不超过200个，所以我们就算所有城市都能去也只有199条路。 int enemy; }citys[199+20]; //同上，不超过200个城市。 int symbol[201]={0}; //标记，如果走过的城市在同一条路线里不会走第二次，因为我们要最快速度最短距离。 int rails=0; //最短距离的路的条数。 int railway[201]; //记录路线 int truerailway[201]; //最终最优路线 int railway_=0; //当前经过的城市的个数 int truerailways=-1; //最优路线经过城市的个数 char cityname[201][4]; //代号转换，将名字转换成数字，后面的conversion函数就是转换功能。 int maxkill=-1; //最优路线歼敌数 int mixdistance=500000; //最短进攻距离 int maxtown=-1; //最优路线解放的城镇的数目 int conversion(char name[4],int N); //城镇代号与数字之间的转化 int compare(char name1[4],char name2[4]); //比较城镇是否相同 void seek(int now ,int distance,int kill,int town); int main() { int N,K; char wgzf; int amount; scanf("%d%d",&N,&K); scanf("%c",&wgzf); scanf("%s",cityname[0]); scanf("%s",cityname[1]); citys[0].arrive_=0; //初始化第一个城镇（即我方大本营） citys[0].enemy=0; //我方大本营没有敌军 amount=N-1; //题目要求N-1条路线 int cityname_=2; //已经初始化了两个城镇，所以从第三个城镇开始计数 while(amount--) //输入，并初始化所有城镇注意由于先前只输入一个敌方大本营，并没有输入敌人人数。 { int number; scanf("%s",cityname[cityname_]); scanf("%d",&number); if(compare(cityname[1],cityname[cityname_])) //判断是否为敌方大本营，是的话初始化敌人个数 { citys[1].enemy=number; citys[1].arrive_=0; } else { citys[cityname_].enemy=number; citys[cityname_].arrive_=0; cityname_++; } } while(K--) //输入路线以及距离（注意两个城镇都要初始化） { char name1[4]; char name2[4]; int distance; scanf("%s",name1); scanf("%s",name2); scanf("%d",&distance); int id1,id2; id1=conversion(name1,N); id2=conversion(name2,N); citys[id1].arrive[citys[id1].arrive_].cityid=id2; citys[id1].arrive[citys[id1].arrive_++].distance=distance; citys[id2].arrive[citys[id2].arrive_].cityid=id1; citys[id2].arrive[citys[id2].arrive_++].distance=distance; } int times; //标记大本营 symbol[0]=1; seek(0,0,0,0); int hh; printf("%s",cityname[0]); for(hh=0;hh%s",cityname[truerailway[hh]]); printf("\n"); printf("%d %d %d",rails,mixdistance,maxkill); } int compare(char name1[4],char name2[4]) //比较函数 { char *p1,*p2; p1=name1; p2=name2; while(*p1==*p2 && *p1!='\0') { p1++; p2++; } if(*p1=='\0') return 1; else return 0; } int conversion(char name[4],int N) //转换函数，转换城镇代号 { int i; for(i=0;i=maxtown) { if(town>maxtown) { maxtown=town; maxkill=kill; truerailways=railway_; int times; for(times=0;timesmaxkill) { maxkill=kill; truerailways=railway_; int times; for(times=0;times

星辰彩虹海🌈 - 数据结构与算法🌳